Составители:
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/
Страницы
- « первая
- ‹ предыдущая
- …
- 51
- 52
- 53
- 54
- 55
- …
- следующая ›
- последняя »
