ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 92
Скачиваний: 0
классе, могут быть исключены из множества А, в результате чего по
лучается автомат с минимальным числом состояний. |
[А, Z, W, |
|
Алгоритм минимизации числа состояний автомата S = |
||
б, к, «і) состоит из следующих шагов. |
я /г, я/;^ 1 |
|
1. Находятся |
последовательные разбиения я р я 2, . . . , |
|
множества А на |
классы одно-, двух-, . . . , /г-, /г 4- 1-эквивалентных |
|
состояний, до тех пор пока на каком-то /г -f 1-м шаге не окажется, что яА , = пк. Нетрудно показать [1], что тогда разбиение я /г = я,
т. е. что /е-эквивалентные состояния являются в этом случае эквива лентными и число шагов /г, при котором я /г = я, не превышает М —1, где М — число элементов в множестве А.
2. В каждом классе эквивалентности разбиения я выбираются по одному элементу, которые образуют множество А' состояний мини
мального автомата S = [А , Z, W, б , к , а.\], эквивалентного авто мату 5.
3. Функции переходов б' и выходов к' автомата S' определяются на множестве А' X Z. Для этого в таблице переходов и выходов вы черкиваются столбцы, соответствующие не вошедшим в множество А' состояниям, а в оставшихся столбцах таблицы переходов все состояния заменяются на эквивалентные из множества А'.
4. В качестве а[ выбирается одно из состояний, эквивалентное состоянию Ö.J. В частности, удобно за а[ принимать само состояние аь В качестве примера рассмотрим минимизацию автомата Мили 5 10,
заданного таблицами переходов и выходов (табл. |
1-10 и 1-11). Непо- |
|||||||
|
|
|
|
|
|
|
Таблица 1-10 |
|
|
Таблица переходов неминимального автомата Мили S10 |
|
||||||
«і |
«2 « 3 |
«4 as |
«<s a 7 |
a e |
« 9 |
a10 |
an |
«12 |
г 1 |
«10 |
«12 |
Zn |
«з |
«s |
« 5 |
a 7 |
« 3 |
« 7 |
a3 |
a iQ |
a ~ |
« 1 |
« 5 |
a 3 |
a Q |
« 1 1 |
« 9 |
a u |
«o |
|
«o |
a 8 |
a g |
«8 |
Таблица 1-11
|
|
Таблица выходов неминимального автомата Мили S10 |
|
|
||||||||
|
«1 |
a 2 |
«3 |
«4 |
«5 |
«0 |
«7 |
«8 |
«9 |
«10 |
«11 |
«12 |
z i |
w L |
w x |
Щ Wn |
w x |
w 2 |
w x |
w x |
w 2 |
Щ |
W2 |
Щ |
|
z 2 |
Wn |
w 2 |
w l |
w l |
w 2 |
w x |
|
w 2 |
Wx |
Wl |
w x |
W1 |
средственно по таблице выходов получаем разбиение я 2 на классы одноэквивалентных состояний, объединяя в эквивалентные классы
одинаковые столбцы: я х = (Аъ В.,}; В л = |
\ал, а„ ад, |
а7, ая\, |
B -, = |
2 Заказ № 2225 |
Госпубл |
чная |
17 |
|
научно-тохіг ческая |
|
|
|
библиотсгѵіа |
СССР |
|
Э КЗЕ М П ЛЯ Р
= (ß3, a4, ав, аа, ß10, ß41, ß12). Действительно, два состояния 1-экви валентны, если их реакции на всевозможные входные слова длины 1 совпадают, т. е. соответствующие этим состояниям столбцы в таблице
выходов должны быть одинаков^. |
заменяя |
состояния в табл. 1-10 |
||||||||||
Строим таблицу |
я 4 (табл. |
1-12), |
||||||||||
соответствующими |
классами |
1-эквивалентности. Очевидно, |
что |
1-эк- |
||||||||
|
|
|
Разбиение я4 состояний автомата S10 |
Таблица 1-12 |
||||||||
|
|
|
|
|
|
|||||||
|
|
|
Ві |
|
|
|
|
|
в 2 |
|
|
|
|
O l |
Оз |
aö |
«7 |
а8 |
о3 |
0.1 |
Оо |
«0 |
аю |
«И |
a12 |
Zl |
Во |
в 3 |
В, |
в 2 |
5о |
в 1 |
Ві |
Ві |
Ві |
Ві |
Bl |
Bl |
*2 |
Вг |
Ві |
в 2 |
в 2 |
Вй |
в 2 |
Вз |
в 2 |
в 2 |
öl |
в 2 |
Bl |
Бивалентные состояния а,п, а$ будут 2-эквивалентными, если они пере водятся любым входным сигналом также в 1-эквивалентные. По
табл. |
1-12 получаем разбиение я 2 на классы 2-эквнвалентных состоя |
||||||||||||
ний (табл. |
1-13): я 2 = (С4, С2, |
С3, С4); |
С4 = |
jüj, а 2), С2 = (а5, а7, |
|||||||||
Сз = |
{ß3, |
ß4, сіе, |
ßg, |
Ац), |
|
С4 = |
(йц, <І12). |
|
|
|
|||
|
|
|
Разбиение л2 |
состояний |
автомата S 10 |
Таблица 1-13 |
|||||||
|
|
|
|
|
|
||||||||
|
C1 |
|
C2 |
|
|
|
|
С3 |
|
|
|
|
|
|
Ol |
a2 |
«5 |
al |
o8 |
|
a3 |
04 |
oe |
Oo |
Oll |
aio |
CI12 |
Zl |
c4 |
Ci |
c3 |
C3 |
Ci |
|
c 2 |
c 2 |
C2 |
c 2 |
Co |
Ci |
Ci |
z2 |
C2 C2 C3 C3 c3 |
|
c3 |
C3 |
c3 |
c3 |
c3 |
Co |
C2 |
||||
Аналогично построим я 3 = |
|
[Dlt |
D.z, D 3, D4, D6); |
D x — [alt |
a 2), |
||||||||
D 2 = |
{ßg, |
ß7) , D 3 — (ßg), |
Di — |
(ß3, |
ß4, |
ß(i, ßg, |
ß ll) , |
D b = |
(ß 4g, |
ßj.2) |
|||
(табл. 1-14) и, |
наконец, я 4 = |
{Elt Е 2, Е 3, Eit |
Е6], которое совпадает |
||||||||||
с я 3. |
Процедура разбиения завершена. |
Разбиение я 3 есть разбиение |
|||||||||||
множества |
состояний |
автомата |
Мили S 10 на |
классы |
эквивалентных |
||||||||
между собой состояний. |
|
|
|
|
|
|
Таблица 1-14 |
||||||
|
|
|
Разбиение я3 состояний автомата S10 |
||||||||||
|
|
|
|
|
|
||||||||
|
Di |
d 2 |
D3 |
|
|
|
Di |
|
|
Db |
|
||
|
Ol |
a2 |
os |
07 |
o8 |
|
a3 |
a4 |
o0 |
CIq |
Oll |
aio |
Ol2 |
Zl |
Db |
Db |
Di |
Di |
Db |
|
d 2 |
d2 |
d2 |
Do |
d 2 |
Di |
Di |
z2 |
d 2 |
d2 |
Di |
Di |
Di |
|
Di |
Di |
Di |
Di |
Di |
D3 |
D3 |
18
Выберем произвольно из каждого класса D lt D 2, D 3, D4, D-a по од
ному состоянию. Пусть, например, |
А' = (o1(. аъ, а8, |
а3, |
а 10). Удаляя |
|||||||||
из первоначальных таблиц переходов (табл. |
1-10) и выходов (табл. |
1-11) |
||||||||||
«лишние» |
состояния а2, а7, ал, |
о0, ав, аХ1, |
а 12, |
определяем минималь |
||||||||
ный |
автомат Мили |
S n |
(таблица |
переходов 1-15 и таблица выходов |
||||||||
1-16), эквивалентный автомату |
5 10. |
|
|
|
|
|
||||||
|
|
|
|
Таблица 1-15 |
|
|
|
|
Таблица |
1-16 |
||
Таблица |
переходов минимального |
|
Таблица |
выходов минимального |
||||||||
|
автомата Мили S13 |
|
|
|
автомата Мили S n |
|
||||||
|
«1 |
Od |
|
Оз |
Я10 |
|
|
а1 |
a-„ |
я8 |
я3 |
°in |
Ч |
"ю |
|
flJ0 |
аь |
0| |
|
Ч |
wx |
|
Wi |
w2 |
Wo |
Zo |
«5 |
«3 |
ая |
я3 |
я* |
|
Zo |
Wo |
w2 |
w2 |
|
W1 |
|
|
|
|
|
|
|
|
|
|
|
Таблица 1-17 |
|
|
Отмеченная таблица переходов неминимального автомата Мура S12 |
|
||||||||||
|
Wi |
WL |
w3 |
w3 |
wa |
Щ |
Щ |
Щ |
Wo |
Wo |
Wo |
Wo |
|
|
|
|
|
|
|
|
|
|
|
■% |
|
|
“1 |
do |
я3 |
аі |
а о |
ае |
а7 |
я8 |
Я9 |
а10 |
ап |
Я12 |
Zl |
°10 |
a l 2 |
аъ |
а1 |
а3 |
а1 |
я3 |
аІ0 |
07 |
Яі |
Яъ |
do |
Zo |
Яз |
Яі |
ав |
■«и |
«9 |
Я11 |
Яо |
Я.1 |
Яо |
Яв |
аа |
Яв |
При минимизации автоматов Мура вводится понятие 0-эквивалент ности состояний и разбиения множества состояний на 0-классы: 0-эк-
вивалентными |
называются |
любые |
|
|
|
Таблица |
1-18 |
|
одинаково отмеченные |
состояния |
|
|
|
||||
автоматов Мура. Есди два 0-эквива- |
Отмеченная |
таблица переходов |
||||||
лентных состояния любым входным |
минимального автомата Мура S13 |
|||||||
сигналом переводятся в два 0-экви- |
|
|
|
|
|
|||
валентных состояния, то они на |
|
К>і |
Wo |
Wo |
w 3 |
|||
зываются 1-эквивалентными. Все |
|
|
|
|
|
|||
дальнейшие классы эквивалентно |
|
Яі |
Яв |
Я ю |
Яз |
|||
сти состояний для автоматов Мура |
|
|
|
|
|
|||
определяются |
аналогично |
приве |
Ч |
а10 |
Я3 |
|
а3 |
|
денному выше для автоматов Ми |
Я і |
|||||||
|
Я3 |
Яв |
|
dß |
||||
ли. В результате применения алго |
ч |
Я і |
||||||
ритма минимизации |
к автомату |
|
|
|
|
|
||
Мура Si а (табл. |
1-17), имеющему 12 |
|
|
|
1-18). Опуская |
|||
состояний, получим автомат S 13 с 4 состояниями (табл. |
||||||||
промежуточные таблицы, приведем лишь последовательность разбие ний:
л0 — (^ li ^ 2> Ba};
2 |
19 |
А = («1. ö2) a&} ’ |
A |
= {flOi aSi |
ö10> ßlli |
а12Іі |
A = {ß3> |
aii |
^b, Ö7}', |
||
|
|
лт = |
{А, |
c 2, |
C3, |
C,jj; |
|
|
|
C i= {fli, Ö2, flg], |
C2= |
[ae, |
ög, flu), |
C3 — jöio, |
Й12), |
|
|
||
|
|
|
|
|
|
|
C,j=(ö3, |
a,j, |
Ö5, 07); |
|
я2=(А , A, A, |
Ai); |
я2= Я!; |
|
|
||||
A = A A = A; A = A; Di = c i . |
|
|
|||||||
1-5. Совмещенная модель автомата (С-автомат)
Под абстрактным С-автоматом будем понимать математическую мо
тов S = [А, Z, W, |
U, ал , б, KltК1г А) , где |
|
|
|
|
|
|
|||
А = |
[ö i, |
а m' |
. . . , |
ам \ — множество состояний; |
сигналов; |
|||||
Z = |
,2 і. |
z t> |
. . , |
zF} — множество |
входных |
|
||||
U7 = |
|
0У„, |
. . . , |
ше) — множество |
выходных |
сигналов |
||||
|
|
|
|
типа 1; |
|
|
|
|
сигналов |
|
U = |
‘1’ |
*/|> • • • , |
Чц! — множество |
выходных |
||||||
|
|
|
|
типа 2; |
|
|
|
|
|
|
а1 6 ^ |
— начальное |
состояние; б — функция |
переходов, реали |
|||||||
зующая отображение множества D6 С А X Z в А; А,х — функция вы |
||||||||||
|
|
|
|
ходов, |
реализующая |
отображение |
||||
t={Zlr.,ZF} |
|
VjAw,,...,wc\ |
множества |
и . |
С А |
х |
Z |
на W; |
||
|
----> |
1 |
|
|
Лі |
|
|
реализую |
||
Ь А= {g;.-,g* |
U={u,,...,Uh\ |
л2 — функция выходов, |
||||||||
|
|
щая |
отображение |
|
множества |
|||||
Рис. 1-14. Абстрактный С-автомат |
|
А на |
U. |
|
|
|
|
|||
Абстрактный С-автомат можно |
||||||||||
(рис. 1-14) |
|
|
|
представить |
в |
виде |
устройства |
|||
с одним входом, на который поступают сигналы |
из вход |
|||||||||
ного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U. Отличие С-автомата от моделей Мили и Мура со стоит в том, что он одновременно реализует две функции выходов Кх и Ко, каждая из которых характерна для этих моделей в отдельности. С-автомат можно описать следующими уравнениями:
a ( t+ 1) = б (а (0 , z(t))\
w(t) = K1(a(t), z(t))\
u(t) = K2(a(t)), t = 0, 1, 2, . . .
Выходной сигнал uh = Ко (am) выдается все время, пока автомат находится в некотором состоянии ат. Выходной сигнал wg = —Ki(am, Zf) выдается во время действия входного сигнала zf при нахо ждении автомата в состоянии ат. Очевидно, что от С-автомата легко перейти к автоматам Мили или Мура (с учетом возможных сдвигов сиг налов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура и наоборот. В то же время в ряде при
20