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

UptoLike

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

50
 ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè ðàñùåïëåíèÿ i-êëàññîâ àâòîìàòà
Ìèëè èëè Ìóðà âîçíèêàþò âñå (i+1)-êëàññû ýòîãî àâòîìàòà (i = 1, 2, ...).
Èìè ÿâëÿåòñÿ âñå ìàêñèìàëüíûå ìíîæåñòâà, âîçíèêàþùèå â ðåçóëüòà-
òå ðàñùåïëåíèÿ.
Åñëè ïðèìåíÿòü ïîñëåäîâàòåëüíî îïåðàöèþ ðàñùåïëåíèÿ i-êëàññîâ
ê êîíå÷íîìó àâòîìàòó Ìèëè èëè Ìóðà, îòïðàâëÿÿñü îò 1-êëàññîâ (äëÿ
àâòîìàòà Ìèëè) èëè îò 0-êëàññîâ (äëÿ àâòîìàòà Ìóðà), òî ÷åðåç êîíå÷-
íîå ÷èñëî øàãîâ äëÿ íåêîòîðîãî k0 ïðîöåññ ðàñùåïëåíèÿ 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
) òàêæå áóäåò ñ÷èòàòüñÿ îïðå-