Лупал А.М. Теория автоматов (часть 1)
Подождите немного. Документ загружается.
51
äåëåííûì, à â êà÷åñòâå ñîñòîÿíèÿ δ
1
(c
m
, z
k
) áóäåò ïðèíèìàòüñÿ ëþáîé
èç ôèíàëüíûõ êëàññîâ c
i
(èõ ìîæåò áûòü íåñêîëüêî), ñîäåðæàùèé âñå
îïðåäåëåííûå ñîñòîÿíèÿ âèäà δ(a
v
, z
k
)(a
v
∈c
m
). Î÷åâèäíî, ôèíàëüíûå
êëàññû c
i
ñ òðåáóåìûìè ñâîéñòâàìè âñåãäà ñóùåñòâóþò.
Çà íà÷àëüíîå ñîñòîÿíèå àâòîìàòà Ñ ìîæíî ïðèíÿòü ëþáîé ôèíàëüíûé
êëàññ, ñîäåðæàùèé íà÷àëüíîå ñîñòîÿíèå àâòîìàòà A, ëèáî ïðèíÿòü çà
íà÷àëüíûå ñîñòîÿíèÿ àâòîìàòà Ñ íåêîòîðûå èëè âñå ôèíàëüíûå êëàñ-
ñû, ñîäåðæàùèå íà÷àëüíîå ñîñòîÿíèå àâòîìàòà A.
Ñîâîêóïíîñòü E âñåõ ôèíàëüíûõ êëàññîâ àâòîìàòà A óäîâëåòâîðÿåò
óñëîâèþ ïîëíîòû è óñëîâèþ çàìêíóòîñòè. Ïåðâîå óñëîâèå îçíà÷àåò, ÷òî
êàæäîå ñîñòîÿíèå àâòîìàòà A ïðèíàäëåæèò êàêîìó-ëèáî èç ôèíàëüíûõ
êëàññîâ. Âòîðîå óñëîâèå îçíà÷àåò, ÷òî äëÿ êàæäîé áóêâû âõîäíîãî àë-
ôàâèòà âñå ñîñòîÿíèÿ êàæäîãî ôèíàëüíîãî êëàññà (ñ òî÷íîñòüþ äî íåî-
ïðåäåëåííûõ ïåðåõîäîâ) ïåðåõîäÿò â ñîñòîÿíèÿ, ïðèíàäëåæàùèå îäíî-
ìó ôèíàëüíîìó êëàññó (òîìó æå ñàìîìó èëè äðóãîìó). Ïóñòü E
0
íàè-
ìåíüøåå ïîäìíîæåñòâî E, óäîâëåòâîðÿþùåå óñëîâèÿì ïîëíîòû è çàì-
êíóòîñòè. Óñëîâèå çàìêíóòîñòè çäåñü îçíà÷àåò, ÷òî äëÿ êàæäîé áóêâû
âõîäíîãî àëôàâèòà âñå ñîñòîÿíèÿ êàæäîãî ôèíàëüíîãî êëàññà èç E
0
(ñ
òî÷íîñòüþ äî íåîïðåäåëåííûõ ïåðåõîäîâ) ïåðåõîäÿò â ñîñòîÿíèÿ, ïðè-
íàäëåæàùèå îäíîìó (òîìó æå ñàìîìó èëè äðóãîìó) ôèíàëüíîìó êëàñ-
ñó èç E
0
. Íàçîâåì ìèíèìàëüíîé íîðìàëüíîé ôîðìîé àâòîìàòà A íîð-
ìàëüíóþ ôîðìó, ïîñòðîåííóþ ïî ìíîæåñòâó ôèíàëüíûõ êëàññîâ E
0
.
Åñëè â ìèíèìàëüíîé íîðìàëüíîé ôîðìå Ñ ñâÿçíîãî àâòîìàòà A â
êà÷åñòâå íà÷àëüíîãî ñîñòîÿíèÿ âûáðàí êàêîé-ëèáî ôèíàëüíûé êëàññ,
ñîäåðæàùèé íà÷àëüíîå ñîñòîÿíèå àâòîìàòà A, òî àâòîìàò Ñ áóäåò èìåòü
íàèìåíüøåå ÷èñëî ñîñòîÿíèé ñðåäè âñåõ àâòîìàòîâ, ýêâèâàëåíòíî ïðî-
äîëæàþùèõ àâòîìàò A.
Ïðîöåññ ìèíèìèçàöèè àâòîìàòà A ìîæíî ðàçáèòü íà äâà ýòàïà. Íà
ïåðâîì ýòàïå ñ ïîìîùüþ êàêîãî-ëèáî ýâðèñòè÷åñêîãî ïðèåìà ñòðîèòñÿ
ýêâèâàëåíòíûé àâòîìàòó A àâòîìàò B ñ ìåíüøèì, ÷åì ó A êîëè÷åñòâîì
ñîñòîÿíèé, à íà âòîðîì ýòàïå ñòàíäàðòíûì ìåòîäîì îñóùåñòâëÿåòñÿ
ìèíèìèçàöèÿ àâòîìàòà A. Ïðè ýòîì ÷åì ìåíüøå êîëè÷åñòâî ñîñòîÿíèé
èìååò àâòîìàò B, òåì ïðîùå áóäåò åãî ïîñëåäóþùàÿ ìèíèìèçàöèÿ.
Íàèáîëüøèé îáúåì ðàáîòû ïî ìèíèìèçàöèè àâòîìàòà ñâÿçàí ñ íà-
õîæäåíèåì ôèíàëüíûõ êëàññîâ. Äëÿ êîíå÷íûõ àâòîìàòîâ ýòà ðàáîòà
ìîæåò áûòü ñóùåñòâåííî óïðîùåíà ñ ïîìîùüþ òðåóãîëüíûõ òàáëèö.
Ïðàâèëà ñîñòàâëåíèÿ è èñïîëüçîâàíèÿ ýòèõ òàáëèö óäîáíåå âñåãî ðàñ-
ñìîòðåòü íà êîíêðåòíûõ ïðèìåðàõ àáñòðàêòíîãî ñèíòåçà àâòîìàòîâ.
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
4
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
53
Àâòîìàò B èìååò òîëüêî 13 ñîñòîÿíèé âìåñòî 21 ñîñòîÿíèÿ ó àâòîìà-
òà A. Ýòè àâòîìàòû ýêâèâàëåíòíû. Äåéñòâèòåëüíî, ïðîéäÿ âñå ïóòè èç
ñîñòîÿíèÿ b
0
÷åðåç äðóãèå ñîñòîÿíèÿ îïÿòü â b
0
, óáåäèìñÿ â òîì, ÷òî
îïåðàòîð àâòîìàòà B îïðåäåëåí íà âñåõ âõîäíûõ ñëîâàõ èç òàáë. 5.3 è
íà èõ íà÷àëüíûõ îòðåçêàõ.
Äðóãèõ ñëîâ îáëàñòü îïðåäåëåíèÿ îïåðàòîðà Â íå ñîäåðæèò. Ïðè ýòîì
êàæäîìó âõîäíîìó ñëîâó îïåðàòîð àâòîìàòà B ñîïîñòàâëÿåò òî æå ñà-
ìîå åäèíñòâåííîå âûõîäíîå ñëîâî, ÷òî è îïåðàòîð àâòîìàòà A.
Òàáëèöà 5.12
Ãðàôó ðèñ. 5.9 ñîîòâåòñòâóåò òàáëèöà ïåðåõîäîâ-âûõîäîâ òàáë. 5.12
àâòîìàòà B. Ôèíàëüíûå êëàññû ýòîãî àâòîìàòà áóäåì èñêàòü ñ ïîìî-
ùüþ òðåóãîëüíîé òàáëèöû (òàáë. 5.13), êîòîðàÿ ñòðîèòñÿ ñëåäóþùèì
îáðàçîì.
Ñòðîêè îáîçíà÷àþòñÿ ñîñòîÿíèÿìè b
1
, b
2
, ..., b
h1
, à ñòîëáöû ñîñòîÿ-
íèÿìè b
0
, b
1
, ..., b
h2
, ãäå h ÷èñëî ñîñòîÿíèé àâòîìàòà. Íà ïåðåñå÷åíèè
i-é ñòðîêè è j-ãî ñòîëáöà çàïèñûâàþòñÿ óñëîâèÿ, ïðè êîòîðûõ âîçìîæíî
ñîâìåùåíèå ñîñòîÿíèé b
i
è b
j
. Åñëè ñîñòîÿíèÿ íåëüçÿ ñîâìåñòèòü íè
ïðè êàêèõ óñëîâèÿõ, ñòàâèòñÿ çíàê ×, åñëè ñîâìåùàþòñÿ áåçóñëîâíî, òî
çíàê ∨. Êëåòêè, ñîîòâåòñòâóþùèå ïåðåñå÷åíèÿì ñòðîê è ñòîëáöîâ ñ îäè-
íàêîâûìè èíäåêñàìè, íå çàïîëíÿþòñÿ. Îêîí÷àòåëüíîå ñîâìåùåíèå ñî-
bt `
α
z
z
b
b
/β b
&
/β
b
b
/β b
#
/β
b
b
!
w/
b
!
w/
b
!
b
"
w/
b
"
b
w/
b
#
b
!
w/
1
b
$
w/
b
$
b
%
w/
b
%
b
w/
b
&
b
'
w/
b
/β
b
'
b
%
w/
b
%
w/
b
b
w/
b
w/
b
b
"
w/
b
b
%
w/
54
ñòîÿíèé îïðåäåëÿåòñÿ íà îñíîâàíèè àíàëèçà íåïðîòèâîðå÷èâîñòè óñëî-
âèé, çàïèñàííûõ â êëåòêàõ. Äëÿ ðàññìàòðèâàåìîãî ïðèìåðà òðåóãîëü-
íàÿ òàáëèöà (òàáë. 5.13) ñòðîèòñÿ ñëåäóþùèì îáðàçîì.
Ñîãëàñíî òàáë. 5.12, ñîñòîÿíèÿì b
0
è b
1
äëÿ êàæäîãî âõîäíîãî ñèãíà-
ëà ñîîòâåòñòâóþò îäèíàêîâûå âûõîäíûå ñèãíàëû, ïîýòîìó ñîñòîÿíèÿ
b
0
è b
1
ìîæíî ñîâìåñòèòü, åñëè ïðè êàæäîì âõîäíîì ñèãíàëå îíè ïåðå-
õîäÿò â ñîâìåñòèìûå ñîñòîÿíèÿ, ò. å. åñëè ìîæíî ñîâìåñòèòü ñîñòîÿ-
íèå b
1
ñ b
2
è ñîñòîÿíèå b
8
ñ b
5
. Ýòè óñëîâèÿ è çàïèñûâàþòñÿ â âåðõíþþ
êëåòêó, ñîîòâåòñòâóþùóþ ñòîëáöó äëÿ b
0
(òàáë. 5.13). Ïîñêîëüêó äëÿ
ñîñòîÿíèé b
0
è b
2
íàéäåòñÿ âõîäíîé ñèãíàë, äëÿ êîòîðîãî (ñì. òàáë. 5.12)
âûäàþòñÿ ðàçëè÷íûå âõîäíûå ñèãíàëû, ýòè ñîñòîÿíèÿ ñîâìåñòèòü íå-
âîçìîæíî, è ñîîòâåòñòâóþùàÿ êëåòêà òàáë. 5.13 îòìå÷àåòñÿ ñèìâî-
ëîì ×. Ñîñòîÿíèÿ b
0
è b
3
ñîâìåùàþòñÿ áåçóñëîâíî, ïîñêîëüêó ïðè êàæ-
äîì âõîäíîì ñèãíàëå ïåðåõîä îïðåäåëåí òîëüêî äëÿ îäíîãî èç íèõ. Â
ñîîòâåòñòâóþùåé êëåòêå òàáë. 5.13 íóæíî ïîñòàâèòü ïîýòîìó ñèìâîë
∨. Çàòåì àíàëèçèðóþòñÿ îñòàëüíûå ïàðû ñîñòîÿíèé ñòîëáöà òàáë. 5.13,
îòìå÷åííîãî ñîñòîÿíèåì b
0
, ïîñëå ÷åãî òî÷íî òàê æå àíàëèçèðóþòñÿ
ïàðû ñîñòîÿíèé, ñîîòâåòñòâóþùèå îñòàëüíûì ñòîëáöàì, íà÷èíàÿ ñ âåð-
õíåé ñòðîêè â êàæäîì ñòîëáöå. Â ðåçóëüòàòå ýòîãî àíàëèçà âñå êëåòêè
òàáë. 5.13 îêàæóòñÿ çàïîëíåííûìè ñèìâîëàìè ×, ∨ èëè óñëîâèÿìè, ïðè
êîòîðûõ âîçìîæíî ñîâìåùåíèå ñîñòîÿíèé, ñîîòâåòñòâóþùèõ êëåò-
êàì. Ïîñëå ýòîãî íà÷èíàåòñÿ àíàëèç óñëîâèé, çàïèñàííûõ â êëåòêàõ
òàáë. 5.13.
Ñîñòîÿíèÿ b
0
è b
1
ìîæíî ñîâìåñòèòü â òîì ñëó÷àå, åñëè ñîâìåñ-
òèìû ñîñòîÿíèÿ b
1
, b
2
è b
5
, b
8
. Íî â êëåòêå, ñîîòâåòñòâóþùåé ñîñòîÿíè-
ÿì b
1
, b
2
, ñòîèò çíàê×, ïîýòîìó ñîâìåñòèòü ñîñòîÿíèÿ b
0
è b
1
íåâîçìîæ-
íî è â ñîîòâåòñòâóþùåé èì êëåòêå ñòàâèòñÿ ñèìâîë ×. Àíàëîãè÷íûì
îáðàçîì íàõîäèì, ÷òî è â êëåòêå, îòìå÷åííîé ñîñòîÿíèÿìè b
2
, b
4
, íóæíî
ïîñòàâèòü çíàê ×.  êëåòêå, îòìå÷åííîé ñîñòîÿíèÿìè b
0
è b
4
, ñòîèò ñèì-
âîë ∨, ïîýòîìó â êëåòêå, îòìå÷åííîé ñîñòîÿíèÿìè b
3
è b
4
, òàê æå íóæíî
ïîñòàâèòü ∨. Â ðåçóëüòàòå ïîñëå òàêîãî àíàëèçà êëåòîê, â êîòîðûõ çàïè-
ñàíû óñëîâèÿ ñîâìåñòèìîñòè, â êàæäîé êëåòêå òàáë. 5.13 áóäåò ñòîÿòü
ñèìâîë × èëè ñèìâîë ∨. Ïî òàêîé òðåóãîëüíîé òàáëèöå ìîæíî íàéòè
ôèíàëüíûå êëàññû.
Ïðîöåäóðà íàõîæäåíèÿ ìèíèìàëüíîãî ìíîæåñòâà ôèíàëüíûõ êëàñ-
ñîâ, ïðåäïîëàãàþùàÿ ïîëíûé ïåðåáîð ñîâìåñòèìûõ ñîñòîÿíèé, ïðèâå-
äåíà â ëèòåðàòóðå [5]. Ïîñêîëüêó ÷àñòî ýòà ïðîöåäóðà îêàçûâàåòñÿ ãðî-
55
ìîçäêîé, ðàññìîòðèì óïðîùåííûé ñïîñîá ôîðìèðîâàíèÿ ìíîæåñòâà
ôèíàëüíûõ êëàññîâ. Ýòîò ñïîñîá, ê ñîæàëåíèþ, íå ãàðàíòèðóåò ïîëó÷å-
íèå îïòèìàëüíîãî ðåçóëüòàòà â ñëó÷àå ÷àñòè÷íîãî àâòîìàòà ñ áîëüøèì
÷èñëîì ñîñòîÿíèé, òàê êàê ñîäåðæèò ýëåìåíòû àëüòåðíàòèâíîãî íåôîð-
ìàëüíîãî âûáîðà ïðè äîîïðåäåëåíèè àâòîìàòà è â ïðîöåññå âêëþ÷åíèÿ
b
b
b,
×
b
#
b,
&
b
××
b
!
∨∨∨
b
"
∨∨∨
b
b,
"
∨
b
#
×××∨∨
b
$
∨∨∨××∨
b
%
∨∨∨××∨
∨
b
&
×××∨∨×∨∨
b
'
×××∨∨×∨∨×
b
×××∨∨×∨∨×
b
%
b,
×
b
%
b,
b
∨∨∨××∨
b
"
b,
%
×
b
b,
"
∨
∨∨∨
b
∨∨∨
b
"
b,
%
×
∨
∨××∨∨∨×
b
b
b
b
!
b
"
b
#
b
$
b
%
b
&
b
'
b
b
Òàáëèöà 5.13
56
êîíêðåòíûõ ñîñòîÿíèé â ôèíàëüíûå êëàññû. Ïðåäëàãàåìûé ñïîñîá ìî-
æåò áûòü îïèñàí ñ ïîìîùüþ ñëåäóþùåé ïðîöåäóðû.
1. Ôîðìèðóåòñÿ ìíîæåñòâî ïàð ñîâìåñòèìûõ ñîñòîÿíèé íà îñíîâà-
íèè ðàçìåòêè êàæäîãî ñòîëáöà òðåóãîëüíîé òàáëèöû.
Äëÿ ðàññìàòðèâàåìîãî àâòîìàòà Ìèëè (òàáë. 5.12) ïî òàáë. 5.13 íà-
õîäèì ñëåäóþùèå ïàðû ñîâìåñòèìûõ ñîñòîÿíèé:
(b
0
, b
3
), (b
1
, b
3
), (b
2
, b
3
), (b
3
, b
4
), (b
4
, b
5
), (b
5
, b
6
),
(b
0
, b
4
), (b
1
, b
4
), (b
2
, b
4
), (b
3
, b
5
), (b
4
, b
8
), (b
5
, b
7
),
(b
0
, b
6
), (b
1
, b
6
), (b
2
, b
6
), (b
3
, b
8
), (b
4
, b
9
), (b
5
, b
11
),
(b
0
, b
7
), (b
1
, b
7
), (b
2
, b
7
), (b
3
, b
9
), (b
4
, b
10
), (b
5
, b
12
),
(b
0
, b
11
), (b
1
, b
11
), (b
2
, b
11
), (b
3
, b
10
), (b
4
, b
12
),
(b
0
, b
12
), (b
1
, b
12
), (b
2
, b
12
),
(b
6
, b
7
), (b
7
, b
8
), (b
8
, b
11
), (b
9
, b
11
), (b
10
, b
11
),
(b
6
, b
8
), (b
7
, b
9
), (b
8
, b
12
), (b
9
, b
12
), (b
10
, b
12
).
(b
6
, b
9
), (b
7
, b
10
),
(b
6
, b
10
), (b
7
, b
11
),
2. Íà îñíîâå ïîëó÷åííîãî ìíîæåñòâà ïðîèçâîäèòñÿ óêðóïíåíèå ãðóïï
ñîâìåñòèìûõ ñîñòîÿíèé, â ðåçóëüòàòå ÷åãî äîëæíà áûòü ïîëó÷åíà ïîë-
íàÿ ñîâîêóïíîñòü ôèíàëüíûõ êëàññîâ, â êàæäîì èç êîòîðûõ âñå ñîñ-
òîÿíèÿ ñîâìåñòèìû ìåæäó ñîáîé. Äëÿ óìåíüøåíèÿ ñëîæíîñòè ýòîé
ïðîöåäóðû âîçìîæíî ïðè ôîðìèðîâàíèè êàæäîãî î÷åðåäíîãî êëàññà
ñîâìåñòèìûõ ñîñòîÿíèé íå ðàññìàòðèâàòü ñîñòîÿíèÿ, óæå âîøåäøèå â
êàêîé-ëèáî èç ñôîðìèðîâàííûõ êëàññîâ.  ÷àñòíîñòè, â ðàññìàòðèâàå-
ìîì ñëó÷àå ñîñòîÿíèå b
0
ñîâìåñòèìî ñ ñîñòîÿíèÿìè b
3
è b
4
, ïðè÷åì
ñîñòîÿíèå b
3
òàê æå ñîâìåñòèìî ñ ñîñòîÿíèåì b
4
, ñëåäîâàòåëüíî, èõ
ìîæíî âêëþ÷èòü â îäèí ôèíàëüíûé êëàññ K
1
. Ñîñòîÿíèå b
0
ñîâìåñòèìî
è ñ ñîñòîÿíèåì b
6
, îäíàêî b
6
íå ñîâìåñòèìî ñ ñîñòîÿíèåì b
3
è íå ìîæåò
âõîäèòü â ýòîò æå ôèíàëüíûé êëàññ. Àíàëîãè÷íàÿ ñèòóàöèÿ îáíàðóæèâà-
åòñÿ ïðè àíàëèçå ñîâìåñòèìûõ ñ b
0
ñîñòîÿíèé b
7
, b
11
, b
12
. Ïîäîáíûì æå
îáðàçîì ôîðìèðóþòñÿ è âñå îñòàëüíûå ôèíàëüíûå êëàññû. Â ðåçóëüòà-
òå áóäóò ïîëó÷åíû ñëåäóþùèå êëàññû ñîâìåñòèìûõ ñîñòîÿíèé:
K
1
= {b
0
, b
3
, b
4
}, K
5
= {b
8
},
K
2
= {b
1
, b
6
, b
7
}, K
6
= {b
9
},
K
3
= {b
2
, b
11
}, K
7
= {b
10
}.
K
4
= {b
5
, b
12
},
57
3. Ïðîèçâîäèòñÿ àíàëèç ïîëó÷åííûõ ôèíàëüíûõ êëàññîâ íà óäîâ-
ëåòâîðåíèå óñëîâèÿì ïîëíîòû è çàìêíóòîñòè. Ïðîâåðêà óñëîâèÿ ïîëíî-
òû î÷åâèäíà è íå âûçûâàåò çàòðóäíåíèé, à ïðîâåðêà óñëîâèÿ çàìêíóòî-
ñòè âûïîëíÿåòñÿ ïî òàáëèöå ïåðåõîäîâ-âûõîäîâ äëÿ âñåõ ñîñòîÿíèé
àâòîìàòà. Åñëè êàêèå-ëèáî äâà ñîñòîÿíèÿ, âõîäÿùèå â îäèí èç âûáðàí-
íûõ ôèíàëüíûõ êëàññîâ, ïåðåâîäÿòñÿ íåêîòîðûì âõîäíûì ñèãíàëîì â
ñîñòîÿíèÿ, ïðèíàäëåæàùèå ðàçíûì êëàññàì, òî íóæíî âûáðàòü íîâîå
ðåøåíèå è ïðîâåðèòü åãî íà çàìêíóòîñòü.
Äëÿ ðàññìàòðèâàåìîãî àâòîìàòà ïðè ïðîâåðêå ôèíàëüíûõ êëàññîâ
íà çàìêíóòîñòü îêàçûâàåòñÿ, ÷òî ïðèíàäëåæàùèå êëàññó K
2
ñîñòîÿíèÿ
b
6
è b
7
ñèãíàëîì a ïåðåâîäÿòñÿ â ñîñòîÿíèÿ, ïðèíàäëåæàùèå ðàçíûì
êëàññàì (b
6
a→ b
7
∈ K
1
, à b
7
a→ b
0
∈ K
2
), ò. å. óñëîâèå çàìêíóòîñòè
íå âûïîëíÿåòñÿ. Ñëåäîâàòåëüíî, íåîáõîäèìî îäíî èç ýòèõ ñîñòîÿíèé (íà-
ïðèìåð, b
7
) ïåðåíåñòè â äðóãîé êëàññ, íå íàðóøàÿ ïðè ýòîì óñëîâèå çàì-
êíóòîñòè. Òàêèì êëàññîì ìîæåò áûòü êëàññ K
5
. Â ðåçóëüòàòå áóäåò
ïîëó÷åíî îêîí÷àòåëüíîå ìíîæåñòâî ôèíàëüíûõ êëàññîâ, ñîâïàäàþùèõ
ñ ñîñòîÿíèÿìè ìèíèìèçèðîâàííîãî àâòîìàòà C
c
0
= K
1
= {b
0
, b
3
, b
4
}, c
3
= K
4
= {b
5
, b
12
}, c
6
= K
7
= {b
10
}.
c
1
= K
2
= {b
1
, b
6
}, c
4
= K
5
= {b
7
, b
8
},
c
0
= K
3
= {b
2
, b
11
}, c
5
= K
6
= {b
9
}.
4. Ñòðîèòñÿ òàáëèöà ïåðåõîäîâ-âûõîäîâ ìèíèìèçèðîâàííîé íîð-
ìàëüíîé ôîðìû çàäàííîãî àâòîìàòà. Äàëåå ïî ýòîé òàáëèöå ìîæíî ïî-
ñòðîèòü ãðàô ïåðåõîäîâ ìèíèìèçèðîâàííîãî àâòîìàòà. Ñîñòîÿíèÿ ïåðå-
õîäîâ è âûõîäíûå ñèãíàëû â ýòîì àâòîìàòå îïðåäåëÿþòñÿ ïî ïåðåõî-
äàì è âûõîäíûì ñèãíàëàì òîãî ñîñòîÿíèÿ, êîòîðîå íàèáîëåå ïîëíî
îïðåäåëåíî.
Òàáëèöà 5.14
c t
α
z
z
c
c
w/
c
/β c
"
/β
c
c
"
w/
c
/β c
!
/β
c
c
w/
c
w/
c
0
w/
c
!
c
"
w/
c
w/
c
w/
c
"
c
0
w/
c
#
w/
c
$
/β
c
#
c
"
w/
c
"
w/
c
$
c
w/
c
!
w/
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
1
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
59
íûìè ñëîâàìè áóäóò ëèøü äâóõáóêâåííîå ñëîâî p
1
= αα, êîòîðîìó
ñîîòâåòñòâóåò âûõîäíîå ñëîâî q
1
= w
0
w
0
è îäíîáóêâåííîå ñëîâî p = α,
êîòîðîìó ñîîòâåòñòâóåò âûõîäíîå ñëîâî q = w
0
. Ñëåäîâàòåëüíî, ñîñòî-
ÿíèÿ a
3
è a
8
ñîâìåñòèìû, è èõ ìîæíî çàìåíèòü îäíèì ñîñòîÿíèåì. Ïå-
ðåîáîçíà÷èâ òåïåðü íà ðèñ. 5.2 a
0
" íà b
0
", a
0
' íà b
0
', a
1
íà b
1
, a
2
íà b
2
, a
5
íà
b
5
, a
7
íà b
6
, a
10
íà b
7
, a
11
íà b
8
, a
12
íà b
9
, a
13
íà b
10
, a
16
íà b
11
, a
19
íà b
12
, a
20
íà b
13
, a
17
íà b
14
, a
18
íà b
15
, ïîëó÷èì ãðàô àâòîìàòà Ìóðà B, èçîáðàæåí-
íûé íà ðèñ. 5.11.
Àâòîìàò B èìååò 17 ñîñòîÿíèé âìåñòî 22 ó àâòîìàòà A è ýòè àâòî-
ìàòû ýêâèâàëåíòíû.
Äåéñòâèòåëüíî, ïðîéäÿ âñå ïóòè èç íà÷àëüíûõ ñîñòîÿíèé ÷åðåç äðó-
ãèå ñîñòîÿíèÿ îïÿòü â íà÷àëüíûå, óáåæäàåìñÿ â òîì, ÷òî îïåðàòîð àâ-
òîìàòà îïðåäåëåí íà âñåõ âõîäíûõ ñëîâàõ èç òàáë. 5.3 è íà íà÷àëüíûõ
îòðåçêàõ è òîëüêî íà íèõ. Ïðè ýòîì êàæäîìó âõîäíîìó ñëîâó îí ñîïîñ-
òàâëÿåò òî æå ñàìîå åäèíñòâåííîå âûõîäíîå ñëîâî, ÷òî è îïåðàòîð àâ-
òîìàòà A.
Ãðàôó ðèñ. 5.11 ñîîòâåòñòâóåò îòìå÷åííàÿ òàáëèöà ïåðåõîäîâ
(òàáë. 5.15) àâòîìàòà B. Ôèíàëüíûå êëàññû àâòîìàòà B áóäåì íàõî-
äèòü ñ ïîìîùüþ òðåóãîëüíîé òàáëèöû (òàáë. 5.16), êîòîðàÿ çàïîëíÿåò-
ñÿ òàê æå, êàê è äëÿ àâòîìàòà Ìèëè. Ôèíàëüíûå êëàññû íàõîäÿòñÿ èç
íåå äëÿ àâòîìàòà Ìóðà ïî òåì æå ïðàâèëàì, ÷òî è àâòîìàòà Ìèëè.
z
1
z
1
z
1
z
1
z
1
z
1
z
1
z
1
z
0
z
0
z
0
z
0
z
0
z
0
z
0
z
0
b
1
0
b
1
4
b
1
5
b
1
3
a
3
b
8
a
5
b
1
2
w
0
w
1
w
1
w
0
w
0
w
0
w
0
w
0
w
1
w
1
b
2
b
6
b
7
b
3
b
1
1
b´
0
b
´
0
b
´
0
b´´
0
b
´
´
0
b
´
´
0
w
0
β
β
β
β
β
αα
αα
α
α
α
α
α
w
1
Ðèñ. 5.11
60
Òàáëèöà 5.15
Èç òàáë. 5.16 èìååì ñëåäóþùèå ïàðû ñîâìåñòèìûõ ñîñòîÿíèé:
(b
0
', b
4
), (b
0
", b
3
), (b
3
, b
15
), (b
4
, b
5
), (b
5
, b
10
),
(b
0
', b
5
), (b
0
", b
8
), (b
4
, b
10
),
(b
0
', b
7
), (b
0
", b
12
),
(b
0
', b
13
), (b
0
", b
15
),
(b
0
', b
14
),
(b
7
, b
10
), (b
10
, b
13
), (b
13
, b
14
).
(b
7
, b
13
), (b
10
, b
14
),
Ïîñëå ïðîâåäåíèÿ óêðóïíåíèÿ ãðóïï ñîâìåñòèìûõ ñîñòîÿíèé ïîëó-
÷èì ôèíàëüíûå êëàññû è ñîîòâåòñòâóþùèå èì ñîñòîÿíèÿ ìèíèìàëüíî-
ãî àâòîìàòà C.
C
0
' = K
1
= {b
0
', b
4
, b
5
}, C
5
= K
7
= {b
8
},
C
0
' = K
2
= {b
0
', b
3
, b
15
}, C
6
= K
8
= {b
9
},
w t b t
α
z
z
w
b
b
b
'
w
b
b
b
'
β
b
b
b
$
β
b
b
3
b
#
w
b
!
b
"
w
b
"
b
w
b
#
b
"
β
b
$
b
!
b
%
w
b
%
b
&
w
b
&
b
β
b
'
b
b
w
b
b
!
b
&
β
b
b
"
b
w
b
b
!
w
b
!
b
w
b
"
b
#
w
b
#
b