Автоматы Мура и Мили

Абстрактные автоматы

Определение:

Абстрактный автомат (АА) является математической моделью дискретного устройства и описывается шестикомпонентным набором [math]S=(A, Z, W, \delta, \lambda, a_{1})[/math], где 1. [math]A=\{a_{1}, ..., a_{m}, ..., a_{M}\}[/math] - множество состояний. 2. [math]Z=\{z_{1}, ..., z_{f}, ..., z_{F}\}[/math] - множество входных сигналов. 3. [math]W=\{w_{1}, ..., w_{g}, ..., w_{G}\}[/math] - множество выходных сигналов. 4. [math]\delta[/math] - функция переходов АА, которая некоторым парам \<состояние - входной сигнал\> ([math]a_{m}[/math], [math]z_{f}[/math]) ставит в соответствие состояние АА [math]a_{s}[/math], т.е. [math]a_{s} = δ(a_{m}, z_{f})[/math], [math]a_{s}\in A[/math]. 5. [math]\lambda[/math] - функция выходов АА, которая некоторым парам \<состояние – входной сигнал\> ([math]a_{m}[/math], [math]z_{f}[/math]) ставит в соответствие выходной сигнал АА [math]w_{g}[/math], т.е. [math]w_{g}=λ(a_{m},z_{f})[/math], [math]w_{g}\in W[/math]. 6. [math]a_{1}[/math] - начальное состояние. АА работает в дискретные моменты времени, и в момент времени [math]t=0[/math] автомат всегда находится в состоянии [math]a_{1}[/math].

Выходные сигналы АА зависят от того, что поступало на его вход раньше.

В каждый момент времени АА, будучи в состоянии [math]a_{m}^{t}[/math], способен воспринимать одну из букв входного алфавита [math]z_{f}^{t}[/math]. В соответствии с функцией [math]\delta[/math], АА перейдет в состояние [math]a_{1}^{t+1}[/math] с выдачей выходного сигнала, который вырабатывается в соответствии с функцией выходов [math]\lambda[/math].

Рассмотрим функционирование автоматов Мура и Мили.

Автомат Мили [math]a(t+1) = \delta (a(t), z(t))[/math] [math]w(t) = \lambda (a(t), z(t))[/math]

Автомат Мура [math]a(t+1) = \delta (a(t), z(t))[/math] [math]w(t) = \lambda (a(t))[/math]

В автоматах Мура выходной сигнал определяется только состоянием автомата в какой-то момент времени и не зависит от входного сигнала в этот же момент времени.

Способы задания автоматов

Табличный способ задания автомата Мили

Автомат Мили может быть задан таблицей переходов и таблицей выходов.

В таблице переходов АА Мили на пересечении столбца [math]a_{m}[/math] и строки [math]z_{f}[/math] записывается состояние [math]a_{s}[/math], которое есть функция [math]\delta[/math] от [math]a_{m}[/math] и [math]z_{f}[/math]

	[math]a_{m}[/math]
[math]z_{f}[/math]	[math]a_{s}[/math]	[math]=\delta (a_{m}, z_{f})[/math]

В таблице выходов на пересечении столбца [math]a_{m}[/math] и строки [math]z_{f}[/math] записывается выходной сигнал, который есть функция [math]\lambda[/math] от [math]a_{m}[/math] и [math]z_{f}[/math].

	[math]a_{m}[/math]
[math]z_{f}[/math]	[math]w_{g}[/math]	[math]=\lambda (a_{m}, z_{f})[/math]

Пример: Задание автомата Мили табличным способом (автомат имеет два входных сигнала, два выходных сигнала и три состояния).

Таблица переходов [math]\delta[/math] [math]a_{1}[/math] [math]a_{2}[/math] [math]a_{3}[/math] [math]z_{1}[/math] [math]a_{1}[/math] [math]a_{3}[/math] [math]a_{1}[/math] [math]z_{2}[/math] [math]a_{2}[/math] [math]a_{1}[/math] [math]a_{2}[/math]

Таблица выходов [math]\lambda[/math] [math]a_{1}[/math] [math]a_{2}[/math] [math]a_{3}[/math] [math]z_{1}[/math] [math]w_{2}[/math] [math]w_{2}[/math] [math]w_{2}[/math] [math]z_{2}[/math] [math]w_{1}[/math] [math]w_{1}[/math] [math]w_{2}[/math]

Графический способ задания автомата Мили

На рисунке приведен граф автомата Мили на 3 состояния, имеющий 2 входных сигнала и 2 выходных сигнала (см. предыдущий пример).

Табличный способ задания автомата Мура

В автомате Мура выходной сигнал зависит только от состояния автомата и не зависит от входного сигнала. Поэтому достаточно для задания автомата Мура в таблице переходов добавить одну строку.

[math]\lambda[/math]	[math]w_{1}[/math]	[math]w_{2}[/math]	[math]w_{1}[/math]	[math]w_{2}[/math]	[math]w_{2}[/math]
[math]\delta[/math]	[math]a_{1}[/math]	[math]a_{2}[/math]	[math]a_{3}[/math]	[math]a_{4}[/math]	[math]a_{5}[/math]
[math]z_{1}[/math]	[math]a_{2}[/math]	[math]a_{2}[/math]	[math]a_{5}[/math]	[math]a_{5}[/math]	[math]a_{2}[/math]
[math]z_{2}[/math]	[math]a_{3}[/math]	[math]a_{3}[/math]	[math]a_{1}[/math]	[math]a_{1}[/math]	[math]a_{4}[/math]

Графический способ задания автомата Мура

На рисунке приведен граф автомата Мура на 5 состояний, имеющий 2 входных сигнала и 2 выходных сигнала.

Реакция автоматов на входное слово

Автомат Мили

Допустим, входное слово [math]\xi[/math] поступает на вход автомата буква за буквой.

Выходное слово [math]\omega[/math] называется реакцией автомата Мили на входное слово [math]\xi[/math] в состоянии [math]a_{1}[/math] (строится по таблице переходов и выходов).

Реакцию автомата на входное слово [math]\xi[/math] можно заменить обходом графа.

Автомат Мура

Выходное слово [math]\omega[/math] называется реакцией автомата Мура на входное слово [math]\xi[/math] в состоянии [math]a_{1}[/math].

В рассматриваемом примере для автоматов Мили и Мура реакции автоматов на одинаковое входное слово совпадают, но они сдвинуты на один такт. Автоматы Мили и Мура дающие одинаковые реакции на одинаковые входные слова называются эквивалентными. Данное замечание приводит к задаче построения эквивалентных автоматов, дающих одинаковые реакции на одинаковые входные слова.

Эквивалентность автоматов Мили и Мура

Переход от автомата Мура к автомату Мили

Шестикомпонентным набором с индексом А будем обозначать автомат Мура, а с индексом В - автомат Мили.

Пусть задан автомат Мура.

Требуется перейти к автомату Мили [math]S_{B} = (A_{B}, Z_{B}, W_{B}, \delta _{B}, \lambda _{B}, a_{1B}[/math]), у которого [math]Z_{A} = Z_{B}[/math], [math]W_{A} = W_{B}[/math], т.е. входные и выходные алфавиты совпадают.

Рассмотрим пример, в котором [math]Z_{А} = \{z_{1}, z_{2}\} = Z_{B}[/math], [math]W_{A} = \{w_{1}, w_{2}\} = W_{B}[/math], [math]a_{1A} = a_{1B}[/math], алфавит состояний автомата Мура содержит четыре элемента.

При переходе от автомата Мура к автомату Мили алфавиты состояний также совпадают, т.е. [math]A_{A} = A_{B}[/math].

Для определения соответствия между функциями переходов выходов автоматов Мура и Мили воспользуемся следующей вспомогательной таблицей.