Автомат Мура

Пример автомата Мура

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

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

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

• множество внутренних состояний S (внутренний алфавит);
• начальное состояние s₀;
• множество входных сигналов X (входной алфавит);
• множество выходных сигналов Y (выходной алфавит)
• функция переходов $\mathrm{\Phi }:S\times X\to S$.
• функция вывода $\mathrm{G}:S\to Y$.

Связь с автоматами Мили

Для любого автомата Мура существует эквивалентный ему автомат Мили: любой автомат Мура путём добавления ряда внутренних состояний может быть преобразован в автомат Мили. Обратное, строго говоря, неверно: дело в том, что сигнал на выходе автомата Мура зависит только от входного сигнала в предыдущие моменты времени, а выходной сигнал для автомата Мили может зависеть от входного сигнала и в текущий момент времени. Для автомата Мили можно в общем случае построить лишь автомат Мура, который ему почти эквивалентен: а именно его выход будет сдвинут во времени на 1. Если мы изменим определение автомата Мура, таким образом, что автомат будет выводить значение $\mathrm{G}(s)$ в конце транзакции $s\to s^{\prime }$, а не в начале, то такие автоматы будут полностью эквивалентны автоматам Мили.

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

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

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

	yШаблон:Sub	yШаблон:Sub	yШаблон:Sub	yШаблон:Sub	yШаблон:Sub	yШаблон:Sub	yШаблон:Sub
	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub
$x_1$	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub
$x_2$	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub	sШаблон:Sub

См. также

• JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата
• Автомат Мура в сравнении с автоматом Мили

Литература

• Karacuba A. A. Experimente mit Automaten (German) // Elektron. Inform.-verarb. Kybernetik, 11, 611—612 (1975).Шаблон:Ref-de
• Карацуба А. А. Решение одной задачи из теории конечных автоматов // УМН, т. 15, № 3(93), с. 157—159 (1960).Шаблон:Ref-ru
• Карацуба А. А. Список научных трудовШаблон:Ref-ru
• Karacuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611—612 (1975).Шаблон:Ref-en
• Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129—153. Princeton University Press, Princeton, N.J.(1956).Шаблон:Ref-en