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

UptoLike

ВУЗ: 

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

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

Рубрика: 

52
5.5. Ïðèìåð ìèíèìèçàöèè àâòîìàòà Ìèëè
Ïóñòü ÷àñòè÷íûé àâòîìàò Ìèëè A çàäàí ãðàôîì, ïðèâåäåííûì íà
ðèñ. 5.1. Ýòî ñâÿçíûé àâòîìàò áåç íåîïðåäåëåííûõ âûõîäíûõ ñèãíàëîâ.
Åãî ìèíèìèçàöèþ áóäåì îñóùåñòâëÿòü â äâà ýòàïà. Ñíà÷àëà ïîñòðîèì
ýêâèâàëåíòíûé àâòîìàòó A àâòîìàò B ñ ìåíüøèì ÷åì ó A ÷èñëîì ñî-
ñòîÿíèé.
Ñîãëàñíî ðèñ. 5.1, åäèíñòâåííûì ïðèìåíèìûì ê ñîñòîÿíèÿì a
4
, a
6
,
a
9
è a
18
âõîäíûì ñëîâîì áóäåò îäíîáóêâåííîå ñëîâî p = α ñ ðåçóëüòà-
òîì ïðèìåíåíèÿ q = w
0
. Ïî ýòîé ïðè÷èíå ñîñòîÿíèÿ a
4
, a
6
, a
9
è a
18
ñî-
âìåñòèìû, è èõ ìîæíî çàìåíèòü îäíèì ñîñòîÿíèåì b
4
. Òî÷íî òàê æå
óáåäèìñÿ â ñîâìåñòèìîñòè ñîñòîÿíèé a
11
, a
14
, a
15
è a
20
, â ñèëó ÷åãî èõ
ìîæíî çàìåíèòü îäíèì ñîñòîÿíèåì b
7
. Äëÿ ñîñòîÿíèé a
3
, a
5
, a
8
ïðèìå-
íèìûìè âõîäíûìè ñëîâàìè áóäóò ëèøü äâóõáóêâåííîå ñëîâî p
1
= αα,
êîòîðîìó ñîîòâåòñòâóåò ðåçóëüòàò ïðèìåíåíèÿ q
1
= w
0
w
0
, è îäíîáóêâåí-
íîå ñëîâî p = α ñ ðåçóëüòàòîì ïðèìåíåíèÿ q = w
0
. Ñëåäîâàòåëüíî, ñî-
ñòîÿíèÿ a
3
, a
5
, a
8
ñîâìåñòèìû, è èõ ìîæíî çàìåíèòü îäíèì ñîñòîÿíèåì
b
3
. Ïåðåîáîçíà÷èâ òåïåðü íà ðèñ. 5.1 a
0
íà b
0
, a
1
íà b
1
, a
2
íà b
2
, a
7
íà b
5
,
a
10
íà b
6
, a
12
íà b
8
, a
13
íà b
9
, a
16
íà b
10
, a
17
íà b
11
è a
19
íà b
12
, ïîëó÷èì
ãðàô àâòîìàòà Ìèëè B, èçîáðàæåííûé íà ðèñ. 5.9.
b
0
b
0
b
0
b
1
b
2
b
5
b
6
b
7
b
3
b
b
8
b
9
b
11
b
1
0
b
1
2
α
/
w
0
α
/
w
0
α
/
w
0
α
/
w
1
α
/
w
1
α
/
w
0
z
/
w
1
0
z
/
w
0
1
z
/
β
0
z
/
β
0
z
/
β
1
z
/
β
1
z
/
β
1
z
/
w
1
0
z
/
w
0
0
z
/
w
1
1
z
/
w
1
1
z
/
w
1
0
z
/
w
0
0
z
/
w
0
1
Ðèñ. 5.9

Страницы