Автомат Мура

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

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

Автомат Мура может быть определен как кортеж из 6 элементов, включающий:

• множество внутренних состояний S (внутренний алфавит)
• начальное состояние S₀
• множество входных сигналов X (входной алфавит)
• множество выходных сигналов Y (выходной алфавит)
• функция переходов Φ(z, x)
• функция выходов Ψ(z, x)

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

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

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

См. также

• Автомат Мура в сравнении с автоматом Мили

Примечания

1. ↑ Moore, Edward F (1956). «Gedanken-experiments on Sequential Machines». Automata Studies,Annals of Mathematical Studies (Princeton University Press) (34): 129–153.

Литература

• Karacuba A. A. Experimente mit Automaten (German) // Elektron. Inform.-verarb. Kybernetik, 11, 611—612 (1975).  (нем.)
• Карацуба А. А. Решение одной задачи из теории конечных автоматов // УМН, т. 15, № 3(93), с. 157—159 (1960).  (рус.)
• Карацуба А. А. Список научных трудов  (рус.)

Для улучшения этой статьи желательно?: Дополнить статью (статья слишком короткая либо содержит лишь словарное определение). Добавить иллюстрации. Проставив сноски, внести более точные указания на источники. Викифицировать список литературы, используя шаблон {{книга}}, и проставить ISBN.