Назад К содержанию Вперед

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

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= Am,zf) и выдаст входной сигнал wg= As). Но соответствующий автомат Мили SB из состояния am, также перейдет в состояние as, поскольку Bm,zf) = Am,zf) = аs- и выдаст тот же выходной сигнал wg согласно способу построения функции В. Таким образом, для входной последовательности длины один поведение автоматов SA и SB полностью совпадает. По индукции нетрудно показать, что любое входное слово конечной длины, поданное на входы автоматов SA и SB , установленных в состояния am, вызовет появление одинаковых выходных слов и, следовательно, автоматы SA и SA аm эквивалентны.

Рис. 1-8. Автомат Мили S6эквивалентный автомату Мура S5


Рис. 1-9. Построение множества As



1.3.5. Переход от А Мили к А Мура

Прежде чем рассмотреть трансформацию автомата-Мили в автомат Мура, наложим на автомат Мили следующее ограничение: у автомата не должно быть преходящих состояний. Под преходящим будем понимать состояние, в которое при представлении автомата в виде графа не входит ни одна дуга, но которое имеет по крайней мере одну выходящую дугу (пример - состояние a1 на рис. 1-3). Итак, пусть задан автомат Мили
SA={AA, ZA, WA, A, A, a1A} ,

где
AA = {а1 , :, аm , : , aM},
ZA= {z1 , :, zf , :, zF},
WA = {w1 , :, wg , : , wG}
;

A - реализует отображение AA х ZA в AA, A - отображение AA на WA , а a1A = a1 - начальное состояние.
Построим автомат Мура
SB={AB, ZB, WB, B, B, a1B},
у которого
ZB= ZA = {z1 , :, zf , :, zF},
WB = WA = {w1 , :, wg , : , wG}
;

Для определения АB каждому состоянию as AA поставим в соответствие множество As всевозможных пар вида s,w g), где wg - выходной сигнал, приписанный входящей в аs дуге (рис. 1-9): Аs={(as, wg) | (am, zf) = as и (am, zf) = wg}
Число элементов в множестве Аs равно числу различных выходных сигналов на дугах автомата S A, входящих в состояние as.
Множество остояний автомата SB получим как обединение множеств AS (s=1,:,M):


Рис. 1-10. Иллюстрация перехода от модели Мили к модели Мура

Функции выходов B и переходов B определим слудиющим образом. Каждому состоянию автомата Мура SB , представляющему собой пару вида (as, Wg), поставим в соответствие выходной сигнал Wg. Если в автомате Мили SA был переход а1B m, zf) = Wk , то в SB (рис. 1-10) будет переход из множества состояний Am , порождаемых am , в состояние (as, Wk) под действием входного сигнала zf.
В качестве начального состояния а1B можно взять любое из состояний множества А1, которое порождается начальным состоянием а1 автомата SA. Напомним, что при сравнении реакции автоматов SA и SB на всевозможные входные слова не должен учитываться выходной сигнал в момент времени t=0, связанный с состоянием а1B автомата SB .


1.3.6. Пример преобразования автомата Мили в автомат Мура

Рассомотрим пример преобразования автомата Мили, изображенного на рис. 1-2, в автомат Мура. В автомате Мили Za={Z1, Z2}, Wa={W1, W2}, Aa= {A1,A2,A3}, а1A= а1, A и A определяются графом автомата. В эквивалентном автомате Мура

ZB = ZA = {Z1, Z2}, WB = WA = {W1, W2}.

1. Построим множество AB , для чего найдем множество пар, порождаемых каждым состоянием автомата SA:
A1={( a1, W1), ( a1, W2)} ={b1,b 2};
A2={( a2, W1)}={b3};
A3={( a3, W1) ( a3, W2)}={b4 ,b5};
AB=A1U A2U A3={b1,b2,b 3,b4,b5}.

2. C каждым состоянием, представляющем собой пару, отождествим выходной сигнал, являющийся вторым элементом этой пары:

B(b1) = B (b3) = B(b4) = W1
B(b2) = B(b5) = W2

3. Рассматривая каждую пару и каждую связь, получим: так как в автомате SA из состояния а1 есть переход под действием сигнала z1 в состояние а3 с выдачей сигнала W1, то из множества A1 = {b1, b2} порождаемых состоянием а1 в автомате Мура SB должен быть переход в состояние {a3, W1}=b4 под действием сигнала z1.

Аналогично с состоянием A1 должен быть переход в состояние {a1, W1} = b1 под действием сигнала z2 и так далее. В качестве начального состояния можно выбрать любую b1,b2 А1. Если сагналы bi заменить на аi, то получим стандартное представление автомата Мура.


1.3.7. Пример перехода от автомата Мили с переходящим состоянием к автомату Мура

Рассмотрим переход от автомата Мили к автомату Мура, у которого входное состояние является переходящим. Будем составлять множество состояний следующим образом:

A1U A2U A3={( a2, W1) ( a2, W2) ( a3, W1) ( a3, W2)} = {b2,b3,b4, b5}.


К этим состояниям добавим пару 1, - ) = b1. Где " - " означает, что выходной сигнал в состоянии b1 не определен. Функцию переходов SB будем определять как и раньше.
Из данного графа получим граф:

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

Методы взаимной транспозиции автоматов Мили и Мура показывают, что при переходе от автомата Мили к автомату Мура число состояний принципиально не меняется. В то время как при обратном переходе в автомат Мура число состояний, как правило, увеличивается. Вследствие транзитивности отношения эквивалентности два автомата Мили, первый из которых получен из автомата Мура, так же будут эквивалентны, но у второго автомата число состояний будет больше. Таким образом эквивалентные между собой автоматы могут иметь различное число состояний. В связи с чем и возникает задача нахождения минимального автомата в классе эквивалентных между собой автоматов. Существование для любого абстрактного автомата эквивалентного ему абстрактного автомата с минимальным числом внутренних состояний впервые было доказано Муром.


1.4. Минимизация полностью определенных автоматов

1.4.1. Теоретические основы минимизации

Рассмотрим алгоритм минимизации полностью определенных абстрактных автоматов Мили, предложенный Ауфенкампом и Хоном. Основная идея этого метода состоит в разбиении всех состояний исходного абстрактного автомата на попарно не пересекающиеся классы эквивалентных состояний и замене каждого класса эквивалентности одним состоянием. Таким образом, получающийся в результате минимальный автомат имеет столько же состояний, на сколько классов эквивалентности разбиваются состояния исходного автомата.
Два состояния автомата аm и аs называются эквивалентными аm ~ аs, если m, ) = s, ) для всевозможных входных слов . Если аm и аs не эквивалентны, они различимы. Более слабой эквивалентностью является k- эквивалентность.
Состояния аm и аs k-эквивалентны аm ~ аs , если m, k) = s, k) для всевозможных входных слов k длины k.
Если состояния не k-эквивалентны, они k-различимы. Введенные отношения эквивалентности и k- эквивалентности рефлексивны, симетричны, транзитивны. Следовательно, они являются отношениями эквивалентности и могут быть использованы для разбиения множества А состояний автомата на попарно не пересекающиеся классы. Соответствующие разбиения на класы эквивалентных и k-эквивалентных состояний будем обозначать и k . Разбиение позволяет определить избыточные элементы в множестве состояний А. Пусть, например, аm и аs эквивалентны. Это значит, что сточки зрения реакций автомата на всевозможные входные слова неважно, находится автомат в состоянии аm или аs, и одно и них, например аs , может быть удалено из множества А. Если каждый класс эквивалентности содержит только одно состояние, множество А несократимо. Если же один или несколько класов содержат более одного элемента, все элементы, кроме одного в каждом класе, могут быть исключены из множества А, в результате чего получается автомат с минимальным числом состояний.


1.4.2. Алгоритм минимизации

Пусть автомат S = {A, Z, W, , , а1} подвергается минимизации. Этот процесс состоит из:

1. Находятся последовательные разбиения 1, 2,:, k, k+1 множества А на классы одно-, двух-,:, k-, k+1 эквивалентных состояний, до тех пор пока на каком-то k+1 шаге не окажется, что k+1= k. Нетрудно показать, что тогда разбиение k = , то есть что k-эквивалентные состояния являются в этом случае эквивалентными и число шагов k, при котором k = не превышает М-1, где М - число элементов в множестве А.

2. В каждом классе эквивалентности разбиения выбираются по одному элементу, которые образуют множество А' состояний минимального автомата S' = {A', Z, W, , , а'1}, эквивалентного автомату S.

3. Функции переходов ' и ' автомата S' определяются на множестве A' x Z. Для этого в таблице переходов и выходов вычеркиваются столбцы, соответсвующие не вошедшим в множество А' состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества A'.

4. В качестве а'1 выбирается одно из состояний, эквивалентное состоянию а1. В частности, удобно за а'1 принимать само а1.


1.4.3. Пример минимизации автомата Мили

T1-10.Таблица переходов не минимального автомата Мили


T1-11. Таблица выходов не минимального автомата Мили


Непосредственно по таблице выходов получаем разбиение 1 на классы одноэквивалентных состояний, объединяя в эквивалентные классы одинаковые столбцы: 1={b1,b2} b1={a1,a 2,a5,a7,a8} b2={a3,a4,a6, a9,a10,a11,a12}. Действительно, два состояния 1- эквивалентны, если их реакции на всевозможные входные слова длины 1 совпадают, то есть соответствующие этим состояниям столбцы в таблице выходов должны быть одинаковы.
Строим таблицу 1 , заменяя состояния в таблице переходов соответствующими классами 1-эквивалентности.

T1-12.Разбиение 1 состояний автомата Мили.


Очевидно, что 1-эквивалентные состояния аm и аs будут 2- эквивалентными, если они переводятся любым входным сигналом также в 1- эквивалентные. По таблице 1-12 получаем разбиение 2={C1,C2,C3,C 4} ; C1= {a1,a2}, C2={a5,a7,a8 }, C3={a3,a4,a6,a9,a11}, C4= {a10,a12}.

T1-13.Разбиение 2 состояний автомата Мили.


Аналогично построим 3 ={D1,D2,D3,D4, D5}; D1={a1,a2}, D2={a5,a7}, D3={a8}, D4={a3,a4,a6,a9,a11 }, D5={a10,a12} и, наконец 4 ={E1 ,E2,E3,E4,E5}, которое совпадает с 3. Процедура разбиения завершена. Разбиение 3 есть разбиение множества состояний автомата Мили на классы эквивалентных между собой состояний.

T1-14.Разбиение 3 состояний автомата Мили.


Вычеркиваем из D1 а2, из D2 а7, из D4 а4, а6, а9, а11, из D5 а12 определяем минимальный автомат Мили.

T1-15.Таблица переходов минимального автомата Мили.


T1-16.Таблица выходов минимального автомата Мили.




1.4.4. Пример минимизации автомата Мура

При минимизации автоматов Мура вводится понятие 0-эквивалентности состояний и разбиение множества состояний на 0-классы: 0-эквивалентными называются любые одинаково отмеченные состояния автоматов Мура. Если два 0-эквивалентных состояния любым входным сигналом переводится в два 0-эквивалентных состояния, то они назаваются 1-эквивалентными. Все дальнейшие классы эквивалентности состояний для автоматов Мура определяются аналогично приведенному выше для автоматов Мили.

T1-17. Отмеченная таблица переходов неминимального автомата Мура.


В результате применения алгоритма минимизации к автомату Мура, имеющему 12 состояний, получим автомат Мура, имеющий 4 состояния. Отпуская промежуточные таблицы, приведем лишь последовательность разбиений: 0 = {B1, B2, B3}.

T1-18. Отмеченная таблица переходов минимального автомата Мура.


B1={a1, a2, a8}; B2={a6, a9, a10, a11, a12}; B3={a3, a4, a5, a7}
1 ={C1, C2, C3, C4}.
C1={ a1, a2, a8}; C2={ a6, a9, a11}; C3={ a10, a12}; C4={ a3, a4, a5, a7}
2 ={D1, D2, D3, D4};
2 = 1;
D1 = C1; D2 = C2; D3 = C3; D4 = C4.



1.5. Совмещенная модель автомата (С- автомат)

Под абстрактным С-автоматом будем понимать математическую модель дискретного устройства, определяемую множеством из 8 элементов

S={A, Z, W, U, a1, , 1, 2} ,где

A={a1,:,am,:,aM} - множество состояний;
Z={z1,:, zf,:,zF}- множество входных сигналов;
W={w1,:,wg,:,wG}- множество выходных сигналов типа 1;
U={u1,:,uh,:,uH}- множество выходных сигналов типа 2;
a1 A - начальное состояние;
- функция переходов, реализующая отображение множества D A x Z в A;
1- функция выходов, реализующая отображение множества D 1 A x Z на W;
2- функция выходов, реализующая отображение множества D 2 A на U.


Рис. 1-14. Абстрактный автомат.

Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих моделей в отдельности. С-автомат можно описать следующими уравнениями:

    a(t+1)=(a(t), z(t));    w(t)= 1(a(t), z(t));    u(t)= 2(a(t)) , t=0,1,2,:

Выходной сигнал uh = 2(аm) выдается все время, пока автомат находится в некотором состоянии аm. Выходной сигнал wg = 1(am, zf) выдается во время действия входного сигнала zf при нахождении автомата в состоянии аm. Очевидно что от С-автомата легко перейти к автоматам Мили или Мура, так же как возможна трансформация автомата Мили в автомат Мура и наоборот. Для создания С-автоматов будем также использовать табличный и графический методы. В первом случае таблица переходов (табл. 1-19) аналогична таблице переходов автомата Мили, а в таблице выходов каждое состояние отмечено соответствующим ему сигналом типа 2 (табл. 1-20). При задании С-автомата в виде графа сигналы типа 1 будем приписывать дугам графа рядом с входными сигналами, а сигналы типа 2- вершинам- состояниям, которым они соответствуют.


Нетрудно показать, что к полностью определенному С-автомату можно применить алгоритм минимизации Ауфенкампа- Хона, если под одноэквивалентными понимать состояния, которые одинаково отмечены и имеют одинаковые столбцы в таблице выходов. Проводя последовательность разбиений на 1-, 2-, :, k-, k+ 1- эквивалентные классы до совпадения разбиений k+ 1 и k получим разбиение множества состояний на эквивалентные, после чего замена каждого класса эквивалентности одном состоянием дает минимальный С-автомат. В результате применения такого алгоритма к автомату, заданному таблицами 1-21 и 1-22, получим минимальный С-автомат, представленный в таблице 1-23 и 1-24. Опуская промежуточные таблицы, приведем лишь последовательность разбиений при минимизации:

1={B1, B2, B3, B4};
B1={a1, a2, a8}; B2={a3, a4}; B3={a5, a7}; B4={a6, a9, a10, a11, a12};
2={C1, C2, C3, C4, C5, C6};
C1={a1, a2}; C2={a8}; C3={a3, a4}; C4={a5, a7}; C5={a6, a9, a11}; C6={a10, a12};
3={D1, D2, D3, D4, D5, D6}=2.

T1-19.Таблица переходов С- автомата.


T1-20.Отмеченная таблица выходов С- автомата.


T1-21.Таблица переходов не минимального С- автомата.


T1-22.Отмеченная таблица выходов не минимального С- автомата.


T1-23.Таблица переходов минимального С- автомата.


T1-24.Отмеченная таблица выходов минимального С- автомата.





Назад К содержанию Вперед

Copyright © 2005  Бобров Максим, Андрющенко Юрий, Лаптева Наталья