Открыть главное меню
Пример автомата Мура

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

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

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

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

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

Для любого автомата Мура существует эквивалентный ему автомат Мили: любой автомат Мура путём добавления ряда внутренних состояний может быть преобразован в автомат Мили. Обратное, строго говоря, неверно: дело в том, что сигнал на выходе автомата Мура зависит только от входного сигнала в предыдущие моменты времени, а выходной сигнал для автомата Мили может зависеть от входного сигнала и в текущий момент времени. Для автомата Мили можно в общем случае построить лишь автомат Мура, который ему почти эквивалентен: а именно его выход будет сдвинут во времени на 1[2]. Если мы изменим определение автомата Мура, таким образом, что автомат будет выводить значение   в конце транзакции  , а не в начале, то такие автоматы будут полностью эквивалентны автоматам Мили.

Способы заданияПравить

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

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

y1 y2 y3 y1 y2 y2 y3
s1 s2 s3 s4 s5 s6 s7
  s5 s4 s5 s3 s4 s2 s5
  s7 s1 s4 s2 s1 s3 s4

См. такжеПравить

ПримечанияПравить

  1. Moore, Edward F. Gedanken-experiments on Sequential Machines (неопр.) // Automata Studies,Annals of Mathematical Studies. — Princeton, N.J.: Princeton University Press, 1956. — № 34. — С. 129—153.
  2. Edward A. Lee and Sanjit A. Seshia. Introduction to Embedded Systems. — Second Edition. — MIT Press, 2017. — P. 58. — ISBN 978-0-262-53381-2.

ЛитератураПравить

  • 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).  (англ.)