Автомат Мура
Формальное определение
Способы задания
Таблица переходов
879.04K
Category: informaticsinformatics

Автомат Мура

1. Автомат Мура

Атырауский инженерно-гуманитарный институт
Автомат Мура
Подготовил: студент 2 курса специальности АиУ
Отегенов Алтынбек
Проверила: старший преподаватель Кубашева Динара
Атырау-2018

2.

Автомат Мура (абстрактный автомат
второго рода) в теории вычислений —
конечный автомат, выходное значение
сигнала в котором зависит лишь от
текущего состояния данного автомата, и не
зависит напрямую, в отличие
от автомата Мили, от входных значений.
Автомат Мура назван в честь
описавшего его свойства Эдварда Ф. Мура,
опубликовавшего исследования в 1956 году
в издании «Gedanken-experiments on
Sequential Machines.»

3. Формальное определение

Автомат Мура может быть определён как кортеж из
6 элементов, включающий:
O множество внутренних состояний S (внутренний
алфавит);
O начальное состояние s0;
O множество входных сигналов X (входной
алфавит);
O множество выходных сигналов Y (выходной
алфавит);
O функция переходов Ф : S × X → S
O функция выводаG : S → Y

4.

Для любого автомата Мура
существует эквивалентный
ему автомат Мили и наоборот.
Любой автомат Мура путём
добавления ряда внутренних
состояний может быть
преобразован в автомат Мили.

5. Способы задания

• Диаграмма — изображённый на плоскости
ориентированный граф, вершины которого
взаимно однозначно соответствуют
состояниям автомата, а дуги — входным
символам.
• Таблица переходов-выходов, в ячейках
которой для каждой пары значений
аргументов х(t), s(t) проставляются будущие
внутренние состояния s(t+1). Значения
выходных сигналов y(t) представляются в
отдельном столбце.

6. Таблица переходов

English     Русский Rules