Составители:
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, òåì ïðîùå áóäåò åãî ïîñëåäóþùàÿ ìèíèìèçàöèÿ.
Íàèáîëüøèé îáúåì ðàáîòû ïî ìèíèìèçàöèè àâòîìàòà ñâÿçàí ñ íà-
õîæäåíèåì ôèíàëüíûõ êëàññîâ. Äëÿ êîíå÷íûõ àâòîìàòîâ ýòà ðàáîòà
ìîæåò áûòü ñóùåñòâåííî óïðîùåíà ñ ïîìîùüþ òðåóãîëüíûõ òàáëèö.
Ïðàâèëà ñîñòàâëåíèÿ è èñïîëüçîâàíèÿ ýòèõ òàáëèö óäîáíåå âñåãî ðàñ-
ñìîòðåòü íà êîíêðåòíûõ ïðèìåðàõ àáñòðàêòíîãî ñèíòåçà àâòîìàòîâ.
Страницы
- « первая
- ‹ предыдущая
- …
- 49
- 50
- 51
- 52
- 53
- …
- следующая ›
- последняя »
