Автомат Мили (Gfmkbgm Bnln)

Перейти к навигации Перейти к поиску
Диаграмма состояний автомата Мили (Граф автомата)

Автомат Мили (англ. 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, 1955. — P. 1045—1079. (англ.)
  • Roth, Charles H., Jr. Fundamentals of Logic Design (англ.). — Thomson-Engineering, 2004. — P. 364—367. — ISBN 0534378048. (англ.)