Автомат Мили

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

Автомат Мили (англ. Mealy machine) — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы.

Автомат Мили — совокупность , где

  • конечное непустое множество состояний автомата;
  • — конечное непустое множество входных символов;
  • — конечное непустое множество выходных символов;
  • — функция переходов, отображающая пары состояние/входной символ на соответствующее следующее состояние;
  • — функция выходов, отображающая пары состояние/входной символ на соответствующий выходной символ;
  • — начальное состояние.

Кодировка автомата Мили:

Вершина (операторная или логическая), стоящая после вершины "Начало", а также вход вершины "Конец" помечается символом S1, вершины, стоящие после операторных помечаются символом Sn (n=2,3..).

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

Матрица функций переходов[править | править вики-текст]

/
q1 q1 / S q2 / U1 q3 / U2
q2 q1 / D1 q2 / S q3 / U1
q3 q1 / D2 q2 / D1 q3 / S

Легенда[править | править вики-текст]

  • — Входные символы;
  • — Внутренние состояния
  • , , — Выходные символы.
  • / — функция перехода

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

Литература[править | править вики-текст]

  • Mealy George H. A Method to Synthesizing Sequential Circuits. — Bell Systems Technical Journal. — P. 1045–1079.  (англ.)
  • Roth Charles H., Jr. Fundamentals of Logic Design. — Thomson-Engineering. — P. 364–367. — ISBN 0534378048.  (англ.)