Автомат Мили

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

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

Автомат Мили — совокупность $\mathit{A}\mathbf{=}\mathbf{(}\mathit{S}\mathbf{,}\mathit{X}\mathbf{,}\mathit{Y}\mathbf{,}\mathit{\delta <!--\; \delta \; -->}\mathbf{,}\mathit{\lambda <!--\; \lambda \; -->}\mathbf{,}{\mathit{S}}_{\mathbf{0}}\mathbf{)}$${\boldsymbol {A=(S,X,Y,\delta ,\lambda ,S_{0})}}$, где

• $S$$S$ — конечное непустое множество состояний автомата;
• $X$$X$ — конечное непустое множество входных символов;
• $Y$$Y$ — конечное непустое множество выходных символов;
• $\mathrm{\delta <!--\; \delta \; -->}:S\times <!--\; \times \; -->X\to <!--\; \to \; -->S$$\delta :S\times X\rightarrow S$ — функция переходов, отображающая пары состояние/входной символ на соответствующее следующее состояние;
• $\mathrm{\lambda <!--\; \lambda \; -->}:S\times <!--\; \times \; -->X\to <!--\; \to \; -->Y$$\lambda :S\times X\rightarrow Y$ — функция выходов, отображающая пары состояние/входной символ на соответствующий выходной символ;
• $S_0\in <!--\; \in \; -->S$$S_{0}\in S$ — начальное состояние.

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

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

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

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

$S$$S$  / $X$$X$	$C_1$$C_{1}$	$C_2$$C_{2}$	$C_3$$C_{3}$
q1	q1 / S	q2 / U1	q3 / U2
q2	q1 / D1	q2 / S	q3 / U1
q3	q1 / D2	q2 / D1	q3 / S

ЛегендаПравить

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

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

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

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

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