Автомат Мили

Диаграмма состояний автомата Мили (Граф автомата)

Автомат Мили (Шаблон:Lang-en) — конечный автомат, выходная последовательность которого (в отличие от автомата Мура) зависит от состояния автомата и входных сигналов. Это означает, что в графе состояний каждому ребру соответствует некоторое значение (выходной символ). В вершины графа автомата Мили записываются выходящие сигналы, а дугам графа приписывают условие перехода из одного состояния в другое, а также входящие сигналы. Назван именем Джорджа Мили, учёного в области математики и компьютерных наук, придумавшего этот автомат.

Автомат Мили — совокупность $𝑨\mathit{=}\mathit{(}𝑺,𝑿,𝒀,\mathit{\delta },\mathit{\lambda },{𝑺}_0\mathit{)}$, где

• $S$ — конечное непустое множество состояний автомата;
• $X$ — конечное непустое множество входных символов;
• $Y$ — конечное непустое множество выходных символов;
• $\delta :S\times X\to S$ — функция переходов, отображающая пары (состояние, входной символ) на соответствующее следующее состояние;
• $\lambda :S\times X\to Y$ — функция выходов, отображающая пары (состояние, входной символ) на соответствующий выходной символ;
• $S_0\in S$ — начальное состояние.

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

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

Представление

Матрица функций переходов

$S$ / $X$	$C_1$	$C_2$	$C_3$
qШаблон:Sub	qШаблон:Sub / S	qШаблон:Sub / UШаблон:Sub	qШаблон:Sub / UШаблон:Sub
qШаблон:Sub	qШаблон:Sub / DШаблон:Sub	qШаблон:Sub / S	qШаблон:Sub / UШаблон:Sub
qШаблон:Sub	qШаблон:Sub / DШаблон:Sub	qШаблон:Sub / DШаблон:Sub	qШаблон:Sub / S

Легенда

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

См. также

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

Литература

• Шаблон:КнигаШаблон:Ref-en
• Шаблон:КнигаШаблон:Ref-en