Составители:
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
Страницы
- « первая
- ‹ предыдущая
- …
- 45
- 46
- 47
- 48
- 49
- …
- следующая ›
- последняя »
