Теория автоматов. Лупал А.М. - 58 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

58
 ðàññìàòðèâàåìîì ïðèìåðå ïîëó÷åíû òàáëèöà ïåðåõîäîâ-âû-
õîäîâ ìèíèìèçèðîâàííîãî àâòîìàòà (òàáë. 5.14) è ãðàô ïåðåõî-
äîâ (ðèñ. 5.10).
5.6. Ïðèìåð ìèíèìèçàöèè àâòîìàòà Ìóðà
Ïóñòü ÷àñòè÷íûé àâòîìàò Ìóðà A çàäàí ãðàôîì, ïðåäñòàâëåí-
íûì íà ðèñ. 5.2. Ïîñêîëüêó âñå ñîñòîÿíèÿ ýòîãî àâòîìàòà äîñòèæè-
ìû, à âûõîäíûå ñèãíàëû îïðåäåëåíû äëÿ âñåõ ñîñòîÿíèé, îòïàäàåò
íåîáõîäèìîñòü èñêëþ÷àòü íåäîñòèæèìûå ñîñòîÿíèÿ. Áóäåì îïÿòü
ìèíèìèçèðîâàòü àâòîìàò â äâà ýòàïà. Ñíà÷àëà ïîñòðîèì ýêâèâàëåí-
òíûé àâòîìàòó A àâòîìàò B ñ ìåíüøèì ÷èñëîì ñîñòîÿíèé.
Ñîãëàñíî ðèñ. 5.2, åñëè àâòîìàò A óñòàíîâëåí â ëþáîå èç ñîñòî-
ÿíèé a
4
, a
6
, a
9
, òî åäèíñòâåííûì äîïóñòèìûì âõîäíûì ñëîâîì áóäåò
îäíîáóêâåííîå ñëîâî p = α, êîòîðîìó ñîîòâåòñòâóåò åäèíñòâåííîå
îäíîáóêâåííîå ñëîâî p = 0. Ïî ýòîé ïðè÷èíå ñîñòîÿíèÿ a
4
, a
6
, a
9
ñî-
âìåñòèìû è èõ ìîæíî çàìåíèòü îäíèì ñîñòîÿíèåì b
4
. Àíàëîãè÷íûì
îáðàçîì íàõîäèì, ÷òî ñîâìåñòèìû ñîñòîÿíèÿ a
11
è a
15
, a
14
è a
20
.
Ïåðâóþ ïàðó çàìåíèì ñîñòîÿíèåì b
8
, âòîðóþ ñîñòîÿíèåì b
13
.
Åñëè àâòîìàò óñòàíîâëåí â ñîñòîÿíèÿ a
3
è a
8
, òî äîïóñòèìûìè âõîä-
c
0
c
1
c
4
c
5
c
6
c
2
c
2
w
0
z
0
z
0
z
z
1
z
1
z
1
z
1
z
1
z
1
z
0
z
0
z
0
z
0
z
0
w
1
w
1
w
1
w
1
w
1
w
1
w
1
w
0
w
0
w
0
w
0
w
0
w
0
α
α
α
α
α
β
β
β
β
β
Ðèñ. 5.10

Страницы