Лупал А.М. Теория автоматов (часть 1)
Подождите немного. Документ загружается.
41
Ïîñêîëüêó â òàáë. 5.1 ïðè z(1) = z
0
äëÿ âòîðîãî è ÷åòâåðòîãî ñëîâ
w(1) = w
0
, à äëÿ ïåðâîãî è òðåòüåãî ñëîâ w(1) = w
1
, äîïèøåì ñïðàâà ê
ïåðâûì ÷åòûðåì âõîäíûì ñëîâàì α è ñëåâà ê ïåðâûì ÷åòûðåì, âûõîä-
íûì ñëîâàì β (òàáë. 5.2). Òî÷íî òàê æå â òàáë. 5.1 ïðè z(1) = z
1
äëÿ
ïÿòîãî, øåñòîãî è ñåäüìîãî ñëîâ w(1) = w
0
, à äëÿ âîñüìîãî ñëîâà w(1) = w
1
,
ïîýòîìó ñïðàâà ê ïÿòîìó, øåñòîìó, ñåäüìîìó è âîñüìîìó âõîäíûì ñëî-
âàì ïðèïèøåì áóêâó α è ñëåâà ê ñîîòâåòñòâóþùèì âûõîäíûì ñëîâàì
ïðèïèøåì áóêâó β. Åñëè ïðè ýòîì ñ÷èòàòü, ÷òî z(1) ïðåîáðàçóåòñÿ â β,
òî äëÿ îäíîáóêâåííûõ íà÷àëüíûõ îòðåçêîâ ñëîâ ïîëó÷èëîñü îäíîçíà÷-
íîå ïðåîáðàçîâàíèå (ñì. òàáë. 5.2).
Òàáëèöà 5.2
Òàáëèöà 5.3
Ðàññìîòðèì äâóõáóêâåííûå íà÷àëüíûå îòðåçêè âõîäíûõ ñëîâ. Îíè
ñîâïàäàþò â ïàðàõ âõîäíûõ ñëîâ (ñì. òàáë. 5.2). Ïîñêîëüêó êîìáèíàöèÿ
z z z ! z " w w w ! w "
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z z z ! z " z # w w w ! w " w #
z
z
z
ααββ
w
w
w
z
z
z
ααββ
w
w
w
z
z
z
ααββ
w
w
w
z
z
z
ααββ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
αβ
w
w
w
z
z
z
ααββ
w
w
w
z
z
z
ααββ
w
w
w
42
z(1)z(2) = z
0
z
0
ïðåîáðàçóåòñÿ íåîäíîçíà÷íî, ñïðàâà îò ïåðâûõ äâóõ âõîä-
íûõ ñëîâ äîïèñûâàåì áóêâó α, à ñëåâà îò ïåðâûõ äâóõ âûõîäíûõ ñëîâ
äîïèñûâàåì áóêâó β (òàáë. 5.3). Òî÷íî òàê æå ïîñòóïàåì ñî âòîðîé è ÷åò-
âåðòîé ïàðàìè âõîäíûõ è âûõîäíûõ ñëîâ. Â òðåòüåé ïàðå ñëîâ êîìáèíàöèÿ
z(1)z(2) = z
1
z
0
ïðåîáðàçóåòñÿ îäíîçíà÷íî (ñì. òàáë. 5.2) â w(1)w(2) = βw
0
.
Ïî ýòîé ïðè÷èíå òðåòüþ ïàðó âõîäíûõ è âûõîäíûõ ñëîâ íå èçìåíÿåì
(ñì. òàáë. 5.3). Òðåõáóêâåííûå íà÷àëüíûå îòðåçêè âõîäíûõ ñëîâ â òàáë.
5.2 âñå ðàçëè÷íû, ïîýòîìó îíè ïðåîáðàçóþòñÿ îäíîçíà÷íî. Òî æå ñàìîå
îòíîñèòñÿ ê ÷åòûðåõáóêâåííûì íà÷àëüíûì îòðåçêàì âõîäíûõ ñëîâ è ê
ïîëíûì âõîäíûì ñëîâàì â òàáë. 5.3. Òàêèì îáðàçîì, çàäàâàåìûé òàáë.
5.3 àëôàâèòíûé îïåðàòîð ϕ, áóäåò àâòîìàòíûì.
Åñëè áû èñõîäíûé îïåðàòîð ñîäåðæàë íå òðåõáóêâåííûå, à ÷åòûðåõáóê-
âåííûå âõîäíûå è âûõîäíûå ñëîâà, äëÿ ïðèâåäåíèÿ åãî ê àâòîìàòíîìó âèäó
òîëüêî ÷òî ðàññìîòðåííûì ñïîñîáîì ïðèøëîñü áû ïðîâåðÿòü îäíîçíà÷íîñòü
ïðåîáðàçîâàíèÿ è òðåõáóêâåííûõ íà÷àëüíûõ îòðåçêîâ âõîäíûõ ñëîâ.
Ïîñòðîèì òåïåðü ïî òàáë. 5.3 ãðàôû àâòîìàòîâ Ìèëè è Ìóðà. Áóäåì
ïðè ýòîì ïðåäïîëàãàòü, ÷òî ïîñëåäíèé ñèìâîë êàæäîãî âõîäíîãî ñëîâà
äîëæåí ïåðåâîäèòü àâòîìàò â íà÷àëüíîå ñîñòîÿíèå. Íà÷íåì ñ ãðàôà
àâòîìàòà Ìèëè (ðèñ. 5.1).
a
1
a
2
a
1
2
a
1
3
a
3
a
4
a
8
a
1
7
a
9
a
1
8
a
1
4
a
7
a
1
6
a
5
a
6
a
1
0
a
1
9
a
1
1
a
2
0
a
1
5
a
0
z
z
z
z
z
/
/
/
/
/
β
β
β
β
β
0
1
1
1
0
z
z
/
/
w
w
0
0
1
1
z
z
z
/
/
/
w
w
w
0
0
0
0
0
0
α
/
w
0
α
/
w
0
α
/
w
0
α
/
w
0
α
/
w
0
α
/
w
0
α
/
w
0
α
/
w
0
α
/
w
1
α
/
w
1
α
/
w
1
α
/
w
1
α
/
w
1
α
/
w
1
z
/
w
1
1
z
z
z
/
/
/
w
w
w
1
1
1
0
0
0
Ðèñ. 5.1
43
 ìîìåíò t = 0 àâòîìàò íàõîäèòñÿ â ñîñòîÿíèè a
0
. Ïðè ïîäà÷å â ïîñ-
ëåäóþùèå ìîìåíòû âðåìåíè êàæäîãî âõîäíîãî ñèãíàëà z(t) àâòîìàò ïå-
ðåõîäèò â íîâîå ñîñòîÿíèå è âûðàáàòûâàåò âûõîäíîé ñèãíàë w(t).
Ïîñêîëüêó äëÿ àáñòðàêòíîãî àâòîìàòà ïîðÿäîê íóìåðàöèè ñîñòîÿíèé,
îòëè÷íûõ îò a
0
, áåçðàçëè÷åí, ìîæíî ñ÷èòàòü, ÷òî áóêâà z(1) = z
0
ïåðâîãî
âõîäíîãî ñëîâà èç òàáë. 5.3 ïåðåâîäèò àâòîìàò â ñîñòîÿíèå a
1
. Ïðè ýòîì
âûðàáàòûâàåòñÿ âûõîäíîé ñèãíàë w(1) = β. Áóêâà z(2) = z
0
ïåðåâîäèò àâòî-
ìàò èç ñîñòîÿíèÿ a
1
â ñîñòîÿíèå a
2
è îáåñïå÷èâàåò âûðàáîòêó âûõîäíîãî
ñèãíàëà w(2) = β. Âõîäíàÿ áóêâà z(3) = z
0
ïåðåâîäèò àâòîìàò èç a
2
â a
3
.
Ýòîìó ïåðåõîäó ñîîòâåòñòâóåò âûõîäíîé ñèãíàë w(3) = w
1
. Áóêâîé z(4) = a
àâòîìàò ïåðåâîäèòñÿ â ñîñòîÿíèå a
4
ñ âûäà÷åé âûõîäíîãî ñèãíàëà w(4) = w
0
.
Ïîñëåäíåé âî âõîäíîì ñëîâå áóêâîé z(5) = a àâòîìàò, ñîãëàñíî óñëîâèþ,
äîëæåí ïåðåâîäèòüñÿ â ñîñòîÿíèå a
0
. Ýòîìó ïåðåõîäó ñîîòâåòñòâóåò âû-
õîäíîé ñèãíàë w(5) = w
0
. Íà÷àëüíûå îòðåçêè z(1)z(2), w(1)w(2) âòîðîãî âõîä-
íîãî è âûõîäíîãî ñëîâ ñîâïàäàþò ñ ñîîòâåòñòâóþùèìè íà÷àëüíûìè îòðåç-
êàìè ïåðâîãî âõîäíîãî è âûõîäíîãî ñëîâ, ïîýòîìó ïåðâûå äâà ïåðåõîäà äëÿ
âòîðîãî âõîäíîãî ñëîâà ñîâïàäàþò ñ óæå ïîñòðîåííûìè. Ïîñëåäóþùèå
ïåðåõîäû äëÿ ýòîãî ñëîâà ñòðîÿòñÿ òî÷íî òàê æå, êàê è äëÿ ïåðâîãî ñëîâà.
Çàòåì àíàëîãè÷íûì îáðàçîì ñòðîÿòñÿ ïåðåõîäû äëÿ îñòàëüíûõ âõîäíûõ è
âûõîäíûõ ñëîâ (ñì. òàáë. 5.3).
Ãðàô àâòîìàòà Ìóðà ïðèâåäåí íà ðèñ. 5.2. Îí ñòðîèòñÿ ïî÷òè òàê
æå, êàê è äëÿ àâòîìàòà Ìèëè. Ïåðâîå îòëè÷èå ñîñòîèò â òîì, ÷òî âû-
õîäíûå ñèãíàëû çàïèñûâàþòñÿ â âåðøèíàõ, òàê êàê âûõîäíîé ñèãíàë
àâòîìàòà Ìóðà â êàæäûé ìîìåíò âðåìåíè îïðåäåëÿåòñÿ òîëüêî
ñîñòîÿíèåì è íå çàâèñèò îò âõîäíîãî ñèãíàëà.
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
a
1
3
a
3
a
2
a
9
a
8
a
1
0
a
1
1
a
1
7
a
1
4
a
5
a
8
a
1
5
a
1
8
a
1
9
a
2
0
w
0
w
1
w
0
w
0
w
1
w
0
w
0
w
0
w
0
w
0
w
0
w
1
w
1
w
1
w
0
a
1
a
2
a
1
2
a
7
a
1
6
a´
0
a
´
0
a
´
0
a
´
0
a
´
0
a´´
0
a
´
´
0
a
´
´
0
a
´
´
0
a
´
´
0
w
0
β
β
β
β
β
αα
αα
α
α
α
αα
αα
αα
α
w
1
Ðèñ. 5.2
44
Âòîðîå îòëè÷èå â ÷èñëå íà÷àëüíûõ ñîñòîÿíèé. Òàê êàê ïîñëåäíÿÿ
áóêâà êàæäîãî âõîäíîãî ñëîâà äîëæíà ïåðåâîäèòü àâòîìàò â íà÷àëüíîå
ñîñòîÿíèå, ïîñëåäíÿÿ áóêâà êàæäîãî âûõîäíîãî ñëîâà ñîîòâåòñòâóåò
íà÷àëüíîìó ñîñòîÿíèþ. Ïîñêîëüêó âûõîäíûå ñëîâà â òàáë. 5.3 ñîäåð-
æàò äâå ðàçëè÷íûå ïîñëåäíèå áóêâû w
0
è w
1
, àâòîìàò äîëæåí èìåòü
äâà ðàâíîïðàâíûõ íà÷àëüíûõ ñîñòîÿíèÿ a
0
'
è a
1
'
, îòìå÷åííûõ âûõîäíûìè
ñèãíàëàìè w
0
è w
1
ñîîòâåòñòâåííî. Ýòè ñîñòîÿíèÿ äîëæíû áûòü ðàâíî-
ïðàâíûìè â òîì ñìûñëå, ÷òî ïðè z(1) = z
0
àâòîìàò èç êàæäîãî èç íèõ
ïåðåõîäèò â ñîñòîÿíèå a
1
, à ïðè z(1) = z
1
àâòîìàò èç êàæäîãî èç íèõ
ïåðåõîäèò â ñîñòîÿíèå a
12
.
Àâòîìàòû, ñîîòâåòñòâóþùèå ðèñ. 5.1 è 5.2, èìåþò âõîäíîé àëôàâèò
{z
0
, z
1
, a}. Òàê êàê èç êàæäîé âåðøèíû ýòèõ ãðàôîâ âûõîäÿò äóãè, îòìå-
÷åííûå íå áîëåå ÷åì äâóìÿ èç ýòèõ ñèìâîëîâ, ðàññìàòðèâàåìûå àâòî-
ìàòû áóäóò ÷àñòè÷íûìè.
Ïî ãðàôàì, èçîáðàæåííûì íà ðèñ. 5.1 è 5.2, ëåãêî ìîæíî ïîñòðî-
èòü òàáëèöû ïåðåõîäîâ è âûõîäîâ àâòîìàòîâ.
5.2. Ïîñòàíîâêà çàäà÷è î ñèíòåçå àâòîìàòîâ
Ñèíòåç àâòîìàòà çàêëþ÷àåòñÿ â ðåàëèçàöèè àâòîìàòà â âèäå óñò-
ðîéñòâà, ñîîòâåòñòâóþùåãî çàäàíèþ. Äëÿ êîíå÷íûõ àâòîìàòîâ çà-
äàíèåì îáû÷íî ñëóæèò ïðåäñòàâëåííûé â âèäå òàáëèöû ñîîòâåòñòâèÿ
àëôàâèòíûé îïåðàòîð. Ïðîöåññ ñèíòåçà ñîñòîèò èç äâóõ ýòàïîâ: ýòà-
ïà àáñòðàêòíîãî ñèíòåçà è ýòàïà ñòðóêòóðíîãî ñèíòåçà.
Íà ýòàïå àáñòðàêòíîãî ñèíòåçà âõîäíûå è âûõîäíûå ñèãíàëû
ðàññìàòðèâàþòñÿ ïðîñòî êàê áóêâû âõîäíîãî è âûõîäíîãî àëôàâè-
òîâ. Ïðè ðàññìîòðåíèè ñîñòîÿíèé èíòåðåñóþòñÿ èõ ÷èñëîì, ñ÷èòàÿ,
÷òî ïðè ìåíüøåì ÷èñëå ñîñòîÿíèé ðåàëèçàöèÿ àâòîìàòà ïðîùå. Ýòîò
ýòàï ñèíòåçà çàêëþ÷àåòñÿ â ïîñòðîåíèè ôóíêöèé ïåðåõîäîâ è âûõî-
äîâ àâòîìàòà ïî çàäàííîìó àëôàâèòíîìó îïåðàòîðó è â íàõîæäåíèè
àáñòðàêòíîãî àâòîìàòà ñ íàèìåíüøèì ÷èñëîì ñîñòîÿíèé â íåêîòî-
ðîì ñìûñëå ýêâèâàëåíòíîãî èñõîäíîìó.
Íà ýòàïå ñòðóêòóðíîãî ñèíòåçà âûáèðàåòñÿ ñïîñîá ïðåäñòàâ-
ëåíèÿ âõîäíûõ è âûõîäíûõ ñèãíàëîâ ÷åðåç ñèãíàëû, ïðèíÿòûå çà
ýëåìåíòàðíûå, à òàêæå ñïîñîá ïðåäñòàâëåíèÿ ñîñòîÿíèé àâòîìà-
òà ÷åðåç ñîñòîÿíèÿ àâòîìàòîâ, ïðèíÿòûõ çà ýëåìåíòàðíûå. Êî-
íå÷íîé öåëüþ ñòðóêòóðíîãî ñèíòåçà ÿâëÿåòñÿ ïîëó÷åíèå ñõåìû,
45
ñîñòîÿùåé èç ìèíèìàëüíîãî ÷èñëà ýëåìåíòîâ çàäàííîãî ëîãè÷åñ-
êîãî áàçèñà.
Âîçìîæíûé ïóòü ðåøåíèÿ ïåðâîé ÷àñòè çàäà÷è àáñòðàêòíîãî
ñèíòåçà óêàçàí â ïîäðàçä. 5.1. Ðåøåíèþ âòîðîé ÷àñòè çàäà÷è íåîáõî-
äèìî ïðåäïîñëàòü íåñêîëüêî îïðåäåëåíèé.
Äâà âïîëíå îïðåäåëåííûõ àáñòðàêòíûõ àâòîìàòà ñ îáùèì âõîä-
íûì è îáùèì âûõîäíûì àëôàâèòàìè íàçûâàþò ýêâèâàëåíòíûìè, åñëè
îíè èìåþò îäèí è òîò æå àëôàâèòíûé îïåðàòîð.
Äâà ÷àñòè÷íûõ àâòîìàòà ñ îáùèì âõîäíûì è îáùèì âûõîäíûì
àëôàâèòàìè íàçûâàþò ýêâèâàëåíòíûìè, åñëè èõ ÷àñòè÷íûå àëôà-
âèòíûå îïåðàòîðû èìåþò îäíó è òó æå îáëàñòü îïðåäåëåíèÿ è
ñîâïàäàþò íà ýòîé îáëàñòè. Äëÿ ÷àñòè÷íûõ àâòîìàòîâ, îäíàêî, áîëü-
øåå çíà÷åíèå èìååò íå îòíîøåíèå ýêâèâàëåíòíîñòè, à îòíîøåíèå ýê-
âèâàëåíòíîãî ïðîäîëæåíèÿ àâòîìàòîâ.
Ãîâîðÿò, ÷òî ÷àñòè÷íûé îïåðàòîð ϕ ïðîäîëæàåò ÷àñòè÷íûé îïå-
ðàòîð ψ, åñëè îáëàñòü îïðåäåëåíèÿ îïåðàòîðà ϕ âêëþ÷àåò â ñåáÿ
îáëàñòü îïðåäåëåíèÿ D îïåðàòîðà ψ, è íà îáëàñòè D îáà îïåðàòîðà
ñîâïàäàþò. ×àñòè÷íûé àâòîìàò B íàçûâàþò ýêâèâàëåíòíûì ïðîäîë-
æåíèåì ÷àñòè÷íîãî àâòîìàòà A, åñëè îïåðàòîð àâòîìàòà  ïðîäîë-
æàåò îïåðàòîð àâòîìàòà A.
Àáñòðàêòíûé ñèíòåç àâòîìàòà çàâåðøàåòñÿ íàõîæäåíèåì àâòî-
ìàòà ñ ìèíèìàëüíûì ÷èñëîì ñîñòîÿíèé, ýêâèâàëåíòíîãî çàäàííîìó
âïîëíå îïðåäåëåííîìó àâòîìàòó èëè ýêâèâàëåíòíî ïðîäîëæàþùåãî
çàäàííûé ÷àñòè÷íûé àâòîìàò. Ïðîöåññ íàõîæäåíèÿ òàêîãî àâòîìàòà
íàçûâàåòñÿ ìèíèìèçàöèåé àáñòðàêòíîãî àâòîìàòà, à ïîëó÷åííûé â
ðåçóëüòàòå åãî àâòîìàò íàçûâàþò ìèíèìàëüíûì àâòîìàòîì.
Ïåðâûì (ïðåäâàðèòåëüíûì) ýòàïîì âñÿêîé ìèíèìèçàöèè ÿâëÿåò-
ñÿ âûäåëåíèå íåîïðåäåëåííûõ âûõîäíûõ ñèãíàëîâ è ñîñòîÿíèé è âíå-
ñåíèå ñîîòâåòñòâóþùåé íåîïðåäåëåííîñòè â òàáëèöû ïåðåõîäîâ è
âûõîäîâ àâòîìàòà òàêèì îáðàçîì, ÷òîáû íå èçìåíèòü îïåðàòîð àâ-
òîìàòà. Ñ ýòîé öåëüþ ïðè çàäàíèè ÷àñòè÷íîãî àâòîìàòà Ìèëè òàá-
ëèöàìè ïåðåõîäîâ è âûõîäîâ íóæíî ïðî÷åðêíóòü âñå ìåñòà â òàáëè-
öå ïåðåõîäîâ àâòîìàòà, êîòîðûì ñîîòâåòñòâóþò ïðî÷åðêíóòûå ìåñ-
òà â òàáëèöå âûõîäîâ. Åñëè äëÿ ÷àñòè÷íûõ àâòîìàòîâ Ìóðà ñ÷èòàòü
çàïðåùåííûìè ñîñòîÿíèÿ, äëÿ êîòîðûõ íå îïðåäåëåíà ôóíêöèÿ âûõî-
äîâ, òî â òàáëèöå ïåðåõîäîâ àâòîìàòà Ìóðà íóæíî çàìåíèòü ÷åðòî÷-
êàìè ñèìâîëû çàïðåùåííûõ ñîñòîÿíèé.
46
Ïóñòü òàáë. 5.4 è 5.5 çàäàþò ôóíêöèè ïåðåõîäîâ è âûõîäîâ ÷àñ-
òè÷íîãî àâòîìàòà Ìèëè.
Òàáëèöà 5.4 Òàáëèöà 5.5 Òàáëèöà 5.6
Åñëè ïðè êàêîì-ëèáî ïåðåõîäå âûõîäíîé ñèãíàë íå îïðåäåëåí, òî è
ñîñòîÿíèå, â êîòîðîå ïåðåéäåò àâòîìàò, íå èìååò çíà÷åíèÿ. Ïîýòîìó
ïîñëå âíåñåíèÿ íåîïðåäåëåííîñòè èç òàáë.5.5 â òàáë.5.4 ïîëó÷èì òàáë.5.6.
Ñîîòâåòñòâóþùèé òàáë.5.4 è òàáë.5.5 ãðàô àâòîìàòà Ìèëè ïðèâåäåí
íà ðèñ. 5.3. Íà ðèñ. 5.4 ïðèâåäåí ãðàô àâòîìàòà, ñîîòâåòñòâóþùèé
òàáë. 5.5 è 5.6.
Åñëè èñõîäíûì ÿâëÿåòñÿ àâòîìàò Ìóðà, çàäàííûé â òàáë. 5.7,
ïîñëå âíåñåíèÿ íåîïðåäåëåííîñòè â òàáëèöó ïåðåõîäîâ, ïîëó÷èì
òàáë. 5.8.
Òàáëèöà 5.7 Òàáëèöà 5.8
Òàáë.5.7 ñîîòâåòñòâóåò ãðàô àâòîìàòà, ïðèâåäåííûé íà ðèñ.5.5, à
òàáë.5.8 ãðàô àâòîìàòà, ïðèâåäåííûé íà ðèñ. 5.6.
a t z
z
a
a
a
a
a
a
a
a
a
a t z
z
a
w
w
a
` w
a
w
`
a t z
z
a
a
a
a
` a
a
a
`
wt ` a t z
z
w
a
a
a
w
a
a
a
a
a
a
wt ` a t z
z
w
a
a
a
w
a
` a
a
a
`
a
0
a
1
a
2
z
/
w
0
1
z
/–
0
z
/–
1
z
/
w
0
0
z
/
w
1
1
z
/
w
1
0
a
0
a
1
a
2
z
/
w
0
1
z
/
w
0
0
z
/
w
1
0
z
/
w
1
1
Ðèñ. 5.3
Ðèñ. 5.4
47
Âòîðûì ýòàïîì ìèíèìèçàöèè ÿâëÿåòñÿ èñêëþ÷åíèå íåäîñòèæèìûõ
ñîñòîÿíèè. Ñîñòîÿíèå a àáñòðàêòíîãî (÷àñòè÷íîãî èëè âïîëíå îïðåäå-
ëåííîãî) àâòîìàòà íàçûâàåòñÿ äîñòèæèìûì, åñëè îíî ñîâïàäàåò ñ íà-
÷àëüíûì ñîñòîÿíèåì èëè åñëè ñóùåñòâóåò òàêîå äîñòèæèìîå ñîñòîÿ-
íèå b è òàêîé âõîäíîé ñèãíàë z, ÷òî a = δ(b, z).  ïðîòèâíîì ñëó÷àå
ñîñòîÿíèå à íàçûâàåòñÿ íåäîñòèæèìûì. Àâòîìàò, âñå ñîñòîÿíèÿ êîòî-
ðîãî äîñòèæèìû, íàçûâàåòñÿ ñâÿçíûì. Äëÿ ïîëó÷åíèÿ ñâÿçíîãî àâòî-
ìàòà íóæíî âû÷åðêíóòü âñå ñòðîêè òàáëèö ïåðåõîäîâ è âûõîäîâ àâòî-
ìàòà, êîòîðûå îáîçíà÷åíû íåäîñòèæèìûìè ñîñòîÿíèÿìè. Âîçìîæíîñòü
óìåíüøåíèÿ ÷èñëà ñîñòîÿíèé íà ýòîì ýòàïå óâåëè÷èâàåòñÿ ïðè óâåëè-
÷åíèè ñòåïåíè íåîïðåäåëåííîñòè, âíåñåííîé â àâòîìàò íà ïåðâîì ýòà-
ïå.
Äëÿ àâòîìàòà Ìèëè, çàäàííîãî òàáë. 5.4, 5.5 èëè ðèñ. 5.3, âñå ñîñòî-
ÿíèÿ äîñòèæèìû, ïîýòîìó àâòîìàò, çàäàííûé òàáë. 5.4, 5.5 èëè ðèñ. 5.3,
áóäåò ñâÿçíûì. Äëÿ àâòîìàòà, çàäàííîãî òàáë. 5.5, 5.6 èëè ðèñ. 5.4, ñî-
ñòîÿíèå a
2
áóäåò íåäîñòèæèìûì, â ñèëó ÷åãî àâòîìàò íå áóäåò ñâÿç-
íûì.
Òî÷íî òàê æå àâòîìàò Ìóðà, çàäàííûé òàáë. 5.7 èëè ðèñ. 5.5, ÿâ-
ëÿåòñÿ ñâÿçíûì, à àâòîìàò, çàäàííûé òàáë. 5.8 èëè ðèñ. 5.6, íå áóäåò
ñâÿçíûì, ïîñêîëüêó ó íåãî ñîñòîÿíèå a
2
íåäîñòèæèìî.
Ïîñëå âû÷åðêèâàíèÿ â òàáë. 5.5, 5.6 è 5.8 ñòðîêè, ñîîòâåòñòâóþùåé
ñîñòîÿíèþ a
2
, ïîëó÷èì ñâÿçíûé àâòîìàò Ìèëè, çàäàííûé òàáë. 5.9, 5.10
èëè ðèñ.5.7, è ñâÿçíûé àâòîìàò Ìóðà, çàäàííûé òàáë. 5.11 èëè ðèñ. 5.8.
Òàáëèöà 5.9 Òàáëèöà 5.10 Òàáëèöà 5.11
z
1
z
1
z
1
z
0
z
0
z
0
a
0
a
2
a
1
w
0
–
w
1
z
1
z
1
z
0
z
0
a
0
a
2
a
1
w
0
–
w
1
Ðèñ. 5.5 Ðèñ. 5.6
a t z
z
a
w
w
a
` w
wt ` a t z
z
w
a
a
a
w
a
` a
a t z
z
a
a
a
a
` a
48
Òðåòüèì ýòàïîì ìèíèìèçàöèè àâòîìàòà ÿâëÿåòñÿ îáúåäèíåíèå â îä-
íî ñîñòîÿíèå ìíîæåñòâà ñîâìåñòèìûõ ñîñòîÿíèé.
5.3. Êëàññû ñîâìåñòèìîñòè àâòîìàòà
Ïóñòü A ïðîèçâîëüíûé àáñòðàêòíûé àâòîìàò, a ëþáîå åãî ñîñòî-
ÿíèå. Ãîâîðÿò, ÷òî ñëîâî p âî âõîäíîì àëôàâèòå àâòîìàòà A ïðèìåíèìî
ê ñîñòîÿíèþ a, åñëè, ïîäàâàÿ ýòî ñëîâî íà âõîä àâòîìàòà A, óñòàíîâëåí-
íîãî ïðåäâàðèòåëüíî â ñîñòîÿíèå à, ìû ïîëó÷èì íà âûõîäå îïðåäåëåí-
íîå ñëîâî q â âûõîäíîì àëôàâèòå, èìåþùåå òó æå ñàìóþ äëèíó, ÷òî
ñëîâî p. Ñëîâî q íàçûâàþò ðåçóëüòàòîì ïðèìåíåíèÿ ñëîâà p ê ñîñòîÿ-
íèþ a.
Åñëè ñëîâî p íåïðèìåíèìî ê ñîñòîÿíèþ à, òî ðåçóëüòàò ïðèìåíåíèÿ
ñëîâà p ê ñîñòîÿíèþ a ñ÷èòàåòñÿ íåîïðåäåëåííûì (ïðè ýòîì áåçðàç-
ëè÷íî, äàþò ëè íåêîòîðûå íåïóñòûå íà÷àëüíûå îòðåçêè ñëîâà p â ïðè-
ìåíåíèè ê ñîñòîÿíèþ à îïðåäåëåííûå ðåçóëüòàòû èëè íåò).
Ñîñòîÿíèÿ a
i1
, ..., a
in
, âõîäÿùèå â àâòîìàò Ìèëè, íàçûâàþòñÿ ñîâìå-
ñòèìûìè, åñëè âñå îïðåäåëåííûå (íå ñ÷èòàÿ íåîïðåäåëåííûõ ðåçóëü-
òàòîâ) ðåçóëüòàòû ïðèìåíåíèÿ ñëîâà p ê ñîñòîÿíèÿì a
i1
, ..., a
in
áóäóò
îäíèìè è òåìè æå (çàâèñÿùèìè òîëüêî îò ñëîâà p, íî íå îò âûáîðà ñî-
ñòîÿíèÿ a
ik
èç äàííîãî ìíîæåñòâà ñîñòîÿíèé). Äëÿ àâòîìàòà Ìóðà, êðî-
ìå ýòîãî óñëîâèÿ, äëÿ ñîâìåñòèìîñòè äàííûõ ñîñòîÿíèé òðåáóåòñÿ, ÷òî-
áû (íå ñ÷èòàÿ íåîïðåäåëåííûõ îòìåòîê) âñå ñîâìåñòèìûå ñîñòîÿíèÿ
èìåëè áû îäèíàêîâûå îòìåòêè. Ñîâìåñòèìûå ñîñòîÿíèÿ âî âïîëíå îï-
ðåäåëåííûõ àâòîìàòàõ íàçûâàþòñÿ òàêæå ýêâèâàëåíòíûìè.
Äëÿ êîíå÷íûõ àâòîìàòîâ ñóùåñòâóåò êîíñòðóêòèâíûé ïðèåì íàõîæ-
äåíèÿ ñîâìåñòèìûõ ñîñòîÿíèè àâòîìàòà Ìèëÿ è Ìóðà. Ýòîò ïðèåì îñ-
íîâàí íà èñïîëüçîâàíèè ïîíÿòèÿ i-ñîâìåñòèìîñòè ñîñòîÿíèé.
Ñîñòîÿíèÿ a
i1
, ..., a
in
àâòîìàòà Ìèëè íàçûâàþòñÿ i-ñîâìåñòèìûìè
äëÿ ëþáîãî äàííîãî i = 1, 2, ..., åñëè (ñ òî÷íîñòüþ äî íåîïðåäåëåííûõ
ðåçóëüòàòîâ) ðåçóëüòàò ïðèìåíåíèÿ ëþáîãî ñëîâà äëèíû i ê ñîñòîÿíèÿì
a
i1
, ..., a
in
áóäåò îäíèì è òåì æå, íàõîäÿñü â çàâèñèìîñòè ëèøü îò âûáî-
a
0
a
1
z
/
w
0
0
z
/
w
1
1
z
/
w
1
0
z
0
z
1
z
1
a
0
a
1
w
0
w
1
Ðèñ. 5.7
Ðèñ. 5.8
49
ðà ñëîâà, íî íå îò âûáîðà ñîñòîÿíèÿ. Ñîñòîÿíèÿ àâòîìàòà Ìóðà íàçûâà-
þòñÿ 0-ñîâìåñòèìûìè, åñëè (íå ñ÷èòàÿ íåîïðåäåëåííûõ îòìåòîê) îíè
îäèíàêîâî îòìå÷åíû; îíè íàçûâàþòñÿ i-ñîâìåñòèìûìè äëÿ ëþáîãî i =
1, 2, ..., åñëè îíè 0-ñîâìåñòèìû è (ñ òî÷íîñòüþ äî íåîïðåäåëåííûõ ðå-
çóëüòàòîâ) ðåçóëüòàò ïðèìåíåíèÿ ëþáîãî äàííîãî ñëîâà äëèíû i êî âñåì
ðàññìàòðèâàåìûì ñîñòîÿíèÿì îäèíàêîâ.
Î÷åâèäíî, i-ñîâìåñòèìûå ñîñòîÿíèÿ áóäóò òàêæå è ϕ-ñîâìåñòèìûìè
äëÿ ëþáîãî j < i. Ñîñòîÿíèÿ òîãäà è òîëüêî òîãäà ñîâìåñòèìû, êîãäà îíè
i-ñîâìåñòèìû äëÿ âñåõ i =1, 2, ... . i-êëàññîì äàííîãî àâòîìàòà Ìèëè è
Ìóðà íàçûâàåòñÿ âñÿêîå ìàêñèìàëüíîå ìíîæåñòâî i-ñîâìåñòèìûõ ìåæ-
äó ñîáîé ñîñòîÿíèé àâòîìàòà, ò. å. òàêîå ìíîæåñòâî, ê êîòîðîìó íåëüçÿ
äîáàâèòü íè îäíîãî íîâîãî ñîñòîÿíèÿ áåç íàðóøåíèÿ ñâîéñòâà i-ñîâìå-
ñòèìîñòè. Âñÿêîå ìàêñèìàëüíîå ìíîæåñòâî ñîâìåñòèìûõ ìåæäó ñî-
áîé ñîñòîÿíèé àâòîìàòà íàçûâàþò ôèíàëüíûì êëàññîì èëè êëàññîì
ñîâìåñòèìîñòè àâòîìàòà.
Íåïîñðåäñòâåííî ïî òàáëèöàì âûõîäîâ ìîãóò áûòü íàéäåíû 1-êëàñ-
ñû äëÿ àâòîìàòîâ Ìèëè è 0-êëàññû äëÿ àâòîìàòîâ Ìóðà.  ñëó÷àå àâ-
òîìàòà Ìèëè â îäèí è òîò æå 1-êëàññ çà÷èñëÿþòñÿ âñå ñîñòîÿíèÿ, îäè-
íàêîâî îáîçíà÷àþùèå (ñ òî÷íîñòüþ äî íåîïðåäåëåííûõ âûõîäíûõ ñèã-
íàëîâ) ñòðîêè òàáëèö âûõîäîâ.  ñëó÷àå àâòîìàòà Ìóðà â îäèí è òîò
æå 0-êëàññ çà÷èñëÿþòñÿ âñå îäèíàêîâî îòìå÷åííûå ñîñòîÿíèÿ è âñå
ñîñòîÿíèÿ, îòìåòêè êîòîðûõ íå îïðåäåëåíû (ïîñëåäíèå ïîïàäàþò, òà-
êèì îáðàçîì, âî âñå 0-êëàññû).
Íà ýòîì ïðèìåðå âèäíî, ÷òî äëÿ ÷àñòè÷íûõ àâòîìàòîâ i-êëàññû, âî-
îáùå ãîâîðÿ, ïåðåñåêàþòñÿ ìåæäó ñîáîé. Òî æå ñàìîå èìååò ìåñòî è
äëÿ ôèíàëüíûõ êëàññîâ. Äëÿ âïîëíå îïðåäåëåííûõ àâòîìàòîâ i-êëàññû
íå ìîãóò ïåðåñåêàòüñÿ ìåæäó ñîáîé.
Ïóñòü K
1
(i), ..., K
p
(i) ñîâîêóïíîñòè âñåõ i-êëàññîâ àâòîìàòà (Ìèëè
èëè Ìóðà). Ãîâîðÿò, ÷òî òîæäåñòâî N ñîñòîÿíèé a
j1
, ..., a
jk
, öåëèêîì ñî-
äåðæàùååñÿ â îäíîì èç i-êëàññîâ K
r
(i) âûäåðæèâàåò óìíîæåíèå íà âõîä-
íóþ áóêâó z
m
, åñëè âñå ñîñòîÿíèÿ δ(a
j1
, z
m
), δ(a
j2
, z
m
), ..., δ(a
jk
, z
m
) (íå
ñ÷èòàÿ òåõ, êîòîðûå íå îïðåäåëåíû) ñîäåðæàòñÿ â îäíîì è òîì æå i-
êëàññå K
t
(i), çàâèñÿùåì îò âûáîðà N è z
m
∈ N.
Íàõîæäåíèå ìàêñèìàëüíûõ ïîäìíîæåñòâ ñîñòîÿíèé êàæäîãî i-êëàññà,
âûäåðæèâàþùèõ óìíîæåíèå íà âñå áóêâû z
1
, z
2
, ..., z
F
âõîäíîãî àëôàâè-
òà àâòîìàòà íàçûâàåòñÿ îïåðàöèåé ðàñùåïëåíèÿ (ðàçáèåíèÿ) i-êëàññîâ.
Îïåðàöèÿ ðàñùåïëåíèÿ i-êëàññîâ âûïîëíÿþòñÿ î÷åâèäíûì îáðàçîì ñ
ïîìîùüþ òàáëèöû ïåðåõîäîâ ðàññìàòðèâàåìîãî àâòîìàòà.
50
 ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè ðàñùåïëåíèÿ i-êëàññîâ àâòîìàòà
Ìèëè èëè Ìóðà âîçíèêàþò âñå (i+1)-êëàññû ýòîãî àâòîìàòà (i = 1, 2, ...).
Èìè ÿâëÿåòñÿ âñå ìàêñèìàëüíûå ìíîæåñòâà, âîçíèêàþùèå â ðåçóëüòà-
òå ðàñùåïëåíèÿ.
Åñëè ïðèìåíÿòü ïîñëåäîâàòåëüíî îïåðàöèþ ðàñùåïëåíèÿ i-êëàññîâ
ê êîíå÷íîìó àâòîìàòó Ìèëè èëè Ìóðà, îòïðàâëÿÿñü îò 1-êëàññîâ (äëÿ
àâòîìàòà Ìèëè) èëè îò 0-êëàññîâ (äëÿ àâòîìàòà Ìóðà), òî ÷åðåç êîíå÷-
íîå ÷èñëî øàãîâ äëÿ íåêîòîðîãî k ≥ 0 ïðîöåññ ðàñùåïëåíèÿ k-êëàññîâ
äàñò â ðåçóëüòàòå òå æå ñàìûå k-êëàññû. Óäîâëåòâîðÿþùèå ýòîìó óñ-
ëîâèþ (íåðàñùåïëÿåìûå äàëåå) k-êëàññû áóäóò ñîâïàäàòü ñ ôèíàëü-
íûìè êëàññàìè èñõîäíîãî àâòîìàòà. Ýòîò ïîëó÷åííûé Â. Ì.Ãëóøêî-
âûì [2] ðåçóëüòàò ÿâëÿåòñÿ îñíîâîé ìèíèìèçàöèè ÷èñëà ñîñòîÿíèé êî-
íå÷íûõ àâòîìàòîâ.
5.4. Àâòîìàò ñ ìèíèìàëüíûì ÷èñëîì ñîñòîÿíèé
Îáîçíà÷èì c
1
, c
2
, ..., c
S
ôèíàëüíûå êëàññû êàêîãî-ëèáî àâòîìàòà A ñ
âõîäíûì àëôàâèòîì Z = {z
1
, z
2
, ..., z
F
}. Òàê êàê ôèíàëüíûå êëàññû ÿâëÿ-
þòñÿ âìåñòå ñ òåì è j-êëàññàìè äëÿ âñåõ j = 0, 1, 2, ..., òî äëÿ êàæäîé
áóêâû z
k
âñå ñîñòîÿíèÿ, âõîäÿùèå â ëþáîé ôèíàëüíûé êëàññ C
m
, ïîðîæ-
äàþò îäèí è òîò æå âûõîäíîé ñèãíàë (äëÿ àâòîìàòà Ìèëè) èëè îòìå÷å-
íû îäíèì è òåì æå âûõîäíûì ñèãíàëîì (äëÿ àâòîìàòà Ìóðà), ëèáî
ñîîòâåòñòâóþùèå âûõîäíûå ñèãíàëû íå îïðåäåëåíû. Ïîñòðîèì òàáëè-
öó âûõîäîâ íåêîòîðîãî àâòîìàòà Ñ, ñîñòîÿíèÿìè êîòîðîãî ñëóæàò ôè-
íàëüíûå êëàññû c
1
, c
2
, ..., c
S
, à âõîäíûìè ñèãíàëàìè áóêâû àëôàâèòà
Z. Äëÿ àâòîìàòà Ìèëè îòíîñèì êàæäîé ïàðå (c
m
, z
k
) âûõîäíîé ñèãíàë,
ñîîòâåòñòâóþùèé ïàðå (a
ν
, z
k
) äëÿ ëþáîãî an èç êëàññà c
m
, äëÿ êîòîðîãî
ýòîò ñèãíàë îïðåäåëåí. Åñëè æå äëÿ âñåõ ïàð (a
ν
, z
k
) ñîîòâåòñòâóþùèå
èì âûõîäíûå ñèãíàëû íå îïðåäåëåíû, òî ñ÷èòàåì, ÷òî âûõîäíîé ñèãíàë
ïàðû (c
m
, z
k
) òàêæå íå îïðåäåëåí. Äëÿ àâòîìàòà Ìóðà îòìå÷àåì êàæ-
äûé êëàññ c
m
âûõîäíûì ñèãíàëîì, êîòîðûì îòìå÷åí ïðîèçâîëüíûé ýëå-
ìåíò a
v
∈ c
m
. Åñëè æå âñå ýëåìåíòû, âõîäÿùèå â c
m
íå îòìå÷åíû, òî
áóäåì ñ÷èòàòü îòìåòêó êëàññà c
m
íåîïðåäåëåííîé.
Òàáëèöó δ
1
ïåðåõîäîâ àâòîìàòà C ïîñòðîèì ïî ñëåäóþùåìó ïðàâè-
ëó: ïåðåõîä èç c
m
â δ
1
(c
m
, z
k
) áóäåò ñ÷èòàòüñÿ íåîïðåäåëåííûì, åñëè äëÿ
ñîñòîÿíèé a
v
, ñîñòàâëÿþùèõ êëàññ c
m
, ïåðåõîä èç a
v
â δ(a
v
, z
k
) íå îïðåäå-
ëåí. Åñëè æå õîòÿ áû äëÿ îäíîãî ñîñòîÿíèÿ a
v
∈ c
m
ïåðåõîä èç a
v
â δ(a
v
,
z
k
) îïðåäåëåí, òî ïåðåõîä èç c
m
â δ
1
(c
m
, z
k
) òàêæå áóäåò ñ÷èòàòüñÿ îïðå-