Автомат Мура

Материал из Википедии — свободной энциклопедии
(перенаправлено с «Диаграмма Мура»)
Перейти к: навигация, поиск

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

Формальное определение[править | править вики-текст]

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

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

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

Способы задания[править | править вики-текст]

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

Таблица переходов[править | править вики-текст]

Y1 Y2 Y3 Y1 Y2 Y2 Y3
a1 a2 a3 a4 a5 a6 a7
1 a5 a4 a5 a3 a4 a2 a5
2 a7 a1 a4 a2 a1 a3 a4

См. также[править | править вики-текст]

Примечания[править | править вики-текст]

  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).  (рус.)
  • Карацуба А. А. Список научных трудов  (рус.)
  • Karacuba A. A. Experimente mit Automaten (German) Elektron. Informationsverarb. Kybernetik, 11, 611–612 (1975).  (англ.)
  • Moore E. F. Gedanken-experiments on Sequential Machines. Automata Studies, Annals of Mathematical Studies, 34, 129–153. Princeton University Press, Princeton, N.J.(1956).  (англ.)