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

UptoLike

ВУЗ: 

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

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

Рубрика: 

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

Страницы