Абстрактные автоматы
1.1. Определение абстрактного автомата
1.2. Методы задания автоматов
1.2.1. Табличный
1.2.2. Графический
1.2.3. Матричный
1.3. Связь между моделями Мили и Мура
1.3.1. Реакция А Мили
1.3.2. Реакция А Мура
1.3.3. Пример
1.3.4. Переход от А Мура к А Мили
1.3.5. Переход от А Мили к А Мура
1.3.6. Пример преобразования автомата Мили в автомат Мура
1.3.7. Пример перехода от автомата Мили с переходящим состоянием к автомату Мура
1.4. Минимизация полностью определенных автоматов
1.4.1. Теоретические основы минимизации
1.4.2. Алгоритм минимизации
1.4.3. Пример минимизации автомата Мили
1.4.4. Пример минимизации автомата Мура
1.5. Совмещенная модель автомата (С-автомат)
1.1. Определение абстрактного автомата 
Математической моделью дискретного управляющего устройства является абстрактный автомат, который задается множеством из шести Элементов: S = {A, Z, W,
,
, а1}, где
А = {а1 ,..., аm ,..., аM} - множество состояний (алфавит1 состояний);
Z = {z1 ,..., zf ,..., zF} - множество входных сигналов (входной алфавит);
W = {w1 ,..., wg ,..., wG} - множество выходных сигналов (выходной алфавит);
- функция переходов, реализующая отображение множества D
А x Z в А (аs =
(аm , zf), аs
А);
- функция выходов, реализующая отображение множества D
А x Z на W (wg =
(аm , zf ));
а1
А - начальное состояние автомата.
Автомат2 называется конечным, если конечны множества А, Z, W. В дальнейшем будут рассматриваться только конечные автоматы и термин <конечный> почти всегда будет опускаться. Автомат называется полностью определенным, если Dб = Dл = А x Z.Иными словами, у полностью определенного автомата области определения функции
и
совпадают со множеством А x Z- множеством всевозможных: пар вида (am, zf ). У частичного автомата функции
или
определены не для всех пар (аm , zf )
А x Z.
Понятие состояния в определение автомата введено в связи с тем, что: возникает необходимость в описании поведения систем, выходы которых зависят не только от состояния входов в данный момент времени, но от некоторой предыстории, т. е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом позволяя устранить время как явную переменную и выразить выходные сигналы, как функцию состояний и входов в данный момент времени.
Абстрактный автомат (рис. 1-1) имеет один входной и один выходной канал. В каждый момент t = 0, 1, 2, . . .дискретного времени автомат находится в определенном состоянии a (t)из множества Асостояний автомата, причем в начальный момент t= 0он всегда находится в начальном состоянии а (0) = а1 . В момент t, будучи в состоянии a (t), автомат способен воспринять на входном канале сигнал z (t)
Z и выдать на выходном канале сигнал w (t) =
(а (t), z (t)), переходя в состояние а (t + 1) =
(а (t), z(t)); а(t)
А, w(t)
W. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Zво множество слов выходного алфавита W. Другими словами, если на вход автомата, установленного в начальное состояние а1, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2), ... -входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита w(0), w(1), w(2),... - выходное слово. Относя к каждому входному слову соответствующее ему выходное слово, мы получим отображение
, индуцированное абстрактным автоматом.
Рис. 1-1. Абстрактный автомат
На практике наибольшее распространение получили автоматы Мили и Мура Закон функционирования автомата Мили задается уравнениями
a(t+1) =
(а(t), z(t)); w(t)=
(a(t), z(t)) , t = 0,1,2,... (1-1)
а закон функционирования автомата Мура - уравнениями
a(t+1) =
(а(t), z(t)); w(t)=
(a(t)) , t = 0,1,2,...
1 Всякий конечный набор попарно различных символов можно рассматривать как некоторый алфавит, буквы которого - указанные символы Конечную упорядоченную последовательность букв назовем словом в данном алфавите.
2 До главы 2 под термином <автомат> понимается абстрактный автомат.
1.2. Методы задания автоматов 
Чтобы задать конечный автомат S, необходимо описать все элементы множества S = {A, Z, W,
,
, а1}, т. е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Среди множества состояний необходимо выделить состояние a1, в котором автомат находится в момент t = 0. Существует несколько способов задания работы автомата, но наиболее часто используются табличный, графический и матричный.
1.2.1. Табличный 
Описание работы автомата Мили таблицами переходов и выходов иллюстрируется таблицами 1-1 и 1-2. Строки этих таблиц соответствуют входным сигналам, а столбцы - состояниям, причем крайний левый столбец состояний обозначен начальным состоянием а1.
Т 1-1 Общий вид таблицы переходов автомата Мили
| Т 1-2 Общий вид таблицы выходов автомата Мили
|
|
|
На пересечении столбца аm и строки zf в таблице переходов ставится состояние аs =
(аm, zf), в которое автомат переходит из состояния аm под действием сигнала zf, а в таблице выходов-соответствующий этому переходу выходной сигнал wg =
(аm, zf). Пример табличного способа задания полностью определенного автомата Мили S1 с тремя состояниями, двумя входными и двумя выходными сигналами приведен в таблицах 1-3 и 1-4.
Т 1-3 Таблица переходов автомата Мили S1
| Т 1-4 Таблица выходов автомата Мили S1
|
|
|
Для частичных автоматов, у которых функции
или
определены не для всех пар (аm, zf)
А х Z, на месте неопределенных состояний и выходных сигналов ставится прочерк (частичный автомат S2 задан таблицами 1-5 и 1-6).
Т 1-5 Таблица переходов частичного автомата Мили S2
| Т 1-6 Таблица выходов частичного автомата Мили S2
|
|
|
Т 1-7 Общий вид отмеченной таблицы переходов автомата Мура
| Т 1-8 Отмеченная таблица .переходов автомата Мура S2
|
|
|
Так как в автомате Мура выходной сигнал зависит, только от состояния, автомат Мура задается одной отмеченной таблицей переходов (таблица 1-7), в которой каждому ее столбцу приписан, кроме состояния аm, еще и выходной сигнал wg =
(аm), соответствующий этому состоянию. Пример табличного описания автомата Мура S3 иллюстрируется таблицей 1-8.
1.2.2. Графический 
Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.
рис. 1-2 Граф автомата Мили S1
| рис. 1-3 Граф автомата Мили S2
|
|
|
Две вершины графа автомата аm и аs (исходное состояние и состояние перехода) соединяются дугой, направленной от аm к аs, если в автомате имеется переход из аm в аs, т. е. если аs =
(аm, zf) при некотором zf
Z. Дуге (аm, аs) графа автомата приписывается входной сигнал zf и выходной сигнал wg =
(аm, zf), если он определен, и ставится прочерк в противном случае. Если переход автомата из состояния аm в состояние а s происходит под действием нескольких входных сигналов, то дуге (аm аs) приписываются все эти входные и соответствующие выходные сигналы. При описании автомата Мура в виде графа выходной сигнал wg =
(аm) записывается внутри вершины или рядом с ней. На рис.1-2, 1-3 и 1-4 приведены заданные ранее таблицами графы автоматов S1, S2, S3.
Рис. 1-4. Граф автомата Мили S3
1.2.3. Матричный 
Матрица соединений автомата есть квадратная матрица
, строки которой соответствуют исходным состояниям, а столбцы - состояниям перехода. Элемент сms= zf / wg, стоящий на пересечении m-ой строки и s-го, в случае автомата Мили соответствует входному сигналу zf, вызывающему переход из состояния аm в состояние аm, и выходному сигналу wg, выдаваемому на этом переходе. Для автомата Мили S1 матрица C1 имеет вид

Если переход из аm в аs происходит под действием нескольких сигналов, элемент сms представляет собой множество пар (вход/выход) для этого перехода, соединенных знаком дизъюнкции. Для модели Мура элемент cms равен множеству входных сигналов на переходе (аm, аs) а выход описывается вектором выходов

m-я компонента которого есть выходной сигнал, отмечающий состояние аm. Для автомата Мура S3

В данной работе рассматриваются только детерминированные автоматы, у которых выполнено условие однозначности переходов: автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к графическому способу задания автомата это означает, что в графе автомата из любой вершины не могут выходить две и более дуги, отмеченные одним и тем же входным сигналом. Аналогично этому в матрице соединений автомата в каждой строке любой входной сигнал не должен встречаться более одного раза.
Т 1-9 Отмеченная таблица переходов асинхронного автомата Мура S 4
|
|
В заключение данного параграфа определим синхронные и асинхронные автоматы. Состояние аs автомата S называется устойчивым состоянием, если для любого входа zf
Z, такого, что
(аm, zf) = аs, имеет место
(аs, zf) = аs.
Автомат S называется асинхронным, если каждое его состояние as
A устойчиво. Автомат S называется синхронным, если он не является асинхронным. Необходимо заметить, что построенные на практике автоматы - всегда асинхронные и устойчивость их состоянии всегда обеспечивается тем или иным способом, например введением сигналов синхронизации (см. ниже, § 3-1).
Рис. 1-5. Граф асинхронного автомата Мура S4
Однако на уровне абстрактной теории, когда автомат есть лишь математическая модель, которая не отражает многих конкретных особенностей его возможной реализации, часто оказывается более удобным оперировать с синхронными автоматами, что мы и будем делать на протяжении всей данной главы. Пример асинхронного автомата Мура S 4 приведен в табл. 1-9 и на рис. 1-5 Нетрудно видеть, что все его состояния устойчивы.
Очевидно, что если в таблице переходов асинхронного автомата некоторое состояние аs стоит на пересечении строки zf и столбца аm (m<>s), то это состояние аs обязательно должно встретиться в этой же строке в столбце аs. В графе асинхронного автомата, если в некоторое состояние имеются переходы из других состояний под действием каких-то сигналов, то в вершине as, должна быть петля, отмеченная символами тех же входных сигналов. Анализ таблиц 1-3, 1-5 и 1-8 или рис. 1-2 - 1-4 показывает, что автоматы S1,S2 и S3 являются синхронными.
1.3. Связь между моделями Мили и Мура 
1.3.1. Реакция А Мили 
В § 1-1 отмечалось, что абстрактный автомат работает как преобразователь слов входного алфавита в слова в выходном алфавите. Остановимся на этом вопросе более подробно, взяв в качестве примера автомат Мили S1 на рис. 1-2 (или табл. 1-3, 1-4). Пусть на вход этого автомата, установленного в начальное состояние, поступает входное слово
= z1z1z2z1z2 z2. Так как
(a1,z1)=a3, а
(a1,z1)=w1,то под действием первой буквы слова
- входного сигнала z1 автомат перейдет в состояние а3 и на выходе его появится сигнал w1. Далее,
(a3,z1)=a1,
(a3,z1)=w 2 и потому при приходе второго сигнала z1 автомат окажется в состоянии a1, а на выходе его появится сигнал w2. Проследив непосредственно по графу или таблицам переходов и выходов дальнейшее поведение автомата, опишем его тремя строчками, первая из которых соответствует входному слову
вторая - последовательности состояний, которые проходит автомат под действием букв слова
, третья - выходному слову W, которое появляется на выходе автомата:

Назовем W =
(а1,
) реакцией автомата Мили в состоянии а1 на входное слово
. Как видно из примера, в ответ на входное слово длины k автомат Мили выдает последовательность состояний длины k+1 и выходное слово длины k. В общем виде поведение автомата установленного в состояние аm, можно описать следующим образом:

1.3.2. Реакция А Мура 
Точно так же можно описать поведение автомата Мура, находящегося в состоянии аm, при приходе входного слова zi1,zi2,:,zik. Напомним, что в соответствии с (1-2) выходной сигнал в автомате Мура в момент времени t(w(t)) зависит лишь от состояния, в котором находится автомат в момент t(а(t)):

Продолжение

Очевидно, что выходной сигнал wi1=
(аm) в момент времени i1 не зависит от входного сигнала zi1, а определяется только состоянием а m. Таким образом, этот сигнал w1 никак не связан с входным словом, поступающим на вход автомата, начиная с момента i1. В связи с этим под реакцией автомата Мура, установленного в состояние аm, на вход-слово
=zi1zi2:zik будем понимать выходное слово той же длины W =
(аm,
)=wi2wi3:wik+1.
1.3.3. Пример 
В качестве примера рассмотрим автомат Мура S5, граф которого изображен на рис. 1-6 и найдем его реакцию в начальном состоянии a1 на то же самое входное слово
= z1z1z2z1z2z2, которое мы использовали при анализе поведения автомата Мили S1:

Как видно из этого и предыдущего примеров, реакции автоматов S5 и S1 в начальном состоянии на входное слово
с точностью до сдвига на 1 такт совпадают. Дадим теперь строгое определение эквивалентности полностью определенных автоматов.
Два автомата SA и SB с одинаковыми входными и выходными алфавитами называются эквивалентными, если после установления их в начальные состояния их реакции на любое входное слово совпадают.
1.3.4. Переход от А Мура к А Мили 
Можно показать [7], что для любого автомата Мили существует эквивалентный ему автомат Мура и, обратно, для любого автомата Мура существует эквивалентный ему автомат Мили. При описании алгоритмов взаимной трансформации автоматов Мили и Мура в соответствии с изложенным выше мы будем пренебрегать в автоматах Мура выходным сигналом, связанным с начальным состоянием
(a1).
Рассмотрим сначала преобразование автомата Мура в автомат Мили. Пусть дан автомат Мура
SA={AA, ZA, WA,
A,
A, a1A} ,
где
AA = {а1 , :, аm , : , aM},
ZA= {z1 , :, zf , :, zF},
WA = {w1 , :, wg , : , wG};
A - реализует отображение AA х Z A в AA,
A - отображение A A на WA, а a1A = a1 - начальное состояние.
Рис. 1-6. Граф автомата Мура S5
Рис. 1-7. Иллюстрация перехода от модели Мура к модели Мили
Построим автомат Мили
SB={AB, ZB, WB,
B ,
B, a1B},
у которого
AB = AA = {а1 , :, аm , : , aM},
ZB= ZA = {z1 , :, zf , :, zF},
WB = WA = {w1 , :, wg , : , wG};
B =
A, a1B = a 1A = a1
Функцию выходов Мили
B определим следующим образом. Если в автомате Мура
A(am,zf)=as и
A(as)=wg, то в автомате Мили
B(am,zf)=wg.
Переход от автомата Мура к автомату Мили при графическом способе задания иллюстрируется рис.1-7: выходной сигнал (wg), записанный рядом с вершиной (аs), переносится на все дуги, входящие в эту вершину. На рис. 1-8 приведен граф автомата Мили S6, эквивалентного автомату Мура S3 (рис. 1-4).
При табличном способе задания автомата SA таблица переходов автомата SB совпадает с таблицей переходов SA, а таблица выходов SB получается из таблицы переходов заменой символа as, стоящего на пересечении строки zf и столбца am, символом выходного сигнала wg, отмечающего столбец as , в таблице переходов автомата SA.
Из самого способа построения автомата Мили SB очевидно, что он эквивалентен автомату Мура SA. Действительно, если некоторый водной сигнал zf
Z поступает на вход автомата SA, находящегося в состоянии аm, то он перейдет в состояние аs=
A(аm,zf) и выдаст входной сигнал wg=
A(аs). Но соответствующий автомат Мили SB из состояния am, также перейдет в состояние as, поскольку
B(аm,zf) =
A(аm,zf) = аs- и выдаст тот же выходной сигнал wg согласно способу построения функции
В. Таким образом, для входной последовательности длины один поведение автоматов SA и SB полностью совпадает. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SA и SB , установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SA аm эквивалентны.