Составители:
45
ñîñòîÿùåé èç ìèíèìàëüíîãî ÷èñëà ýëåìåíòîâ çàäàííîãî ëîãè÷åñ-
êîãî áàçèñà.
Âîçìîæíûé ïóòü ðåøåíèÿ ïåðâîé ÷àñòè çàäà÷è àáñòðàêòíîãî
ñèíòåçà óêàçàí â ïîäðàçä. 5.1. Ðåøåíèþ âòîðîé ÷àñòè çàäà÷è íåîáõî-
äèìî ïðåäïîñëàòü íåñêîëüêî îïðåäåëåíèé.
Äâà âïîëíå îïðåäåëåííûõ àáñòðàêòíûõ àâòîìàòà ñ îáùèì âõîä-
íûì è îáùèì âûõîäíûì àëôàâèòàìè íàçûâàþò ýêâèâàëåíòíûìè, åñëè
îíè èìåþò îäèí è òîò æå àëôàâèòíûé îïåðàòîð.
Äâà ÷àñòè÷íûõ àâòîìàòà ñ îáùèì âõîäíûì è îáùèì âûõîäíûì
àëôàâèòàìè íàçûâàþò ýêâèâàëåíòíûìè, åñëè èõ ÷àñòè÷íûå àëôà-
âèòíûå îïåðàòîðû èìåþò îäíó è òó æå îáëàñòü îïðåäåëåíèÿ è
ñîâïàäàþò íà ýòîé îáëàñòè. Äëÿ ÷àñòè÷íûõ àâòîìàòîâ, îäíàêî, áîëü-
øåå çíà÷åíèå èìååò íå îòíîøåíèå ýêâèâàëåíòíîñòè, à îòíîøåíèå ýê-
âèâàëåíòíîãî ïðîäîëæåíèÿ àâòîìàòîâ.
Ãîâîðÿò, ÷òî ÷àñòè÷íûé îïåðàòîð ϕ ïðîäîëæàåò ÷àñòè÷íûé îïå-
ðàòîð ψ, åñëè îáëàñòü îïðåäåëåíèÿ îïåðàòîðà ϕ âêëþ÷àåò â ñåáÿ
îáëàñòü îïðåäåëåíèÿ D îïåðàòîðà ψ, è íà îáëàñòè D îáà îïåðàòîðà
ñîâïàäàþò. ×àñòè÷íûé àâòîìàò B íàçûâàþò ýêâèâàëåíòíûì ïðîäîë-
æåíèåì ÷àñòè÷íîãî àâòîìàòà A, åñëè îïåðàòîð àâòîìàòà  ïðîäîë-
æàåò îïåðàòîð àâòîìàòà A.
Àáñòðàêòíûé ñèíòåç àâòîìàòà çàâåðøàåòñÿ íàõîæäåíèåì àâòî-
ìàòà ñ ìèíèìàëüíûì ÷èñëîì ñîñòîÿíèé, ýêâèâàëåíòíîãî çàäàííîìó
âïîëíå îïðåäåëåííîìó àâòîìàòó èëè ýêâèâàëåíòíî ïðîäîëæàþùåãî
çàäàííûé ÷àñòè÷íûé àâòîìàò. Ïðîöåññ íàõîæäåíèÿ òàêîãî àâòîìàòà
íàçûâàåòñÿ ìèíèìèçàöèåé àáñòðàêòíîãî àâòîìàòà, à ïîëó÷åííûé â
ðåçóëüòàòå åãî àâòîìàò íàçûâàþò ìèíèìàëüíûì àâòîìàòîì.
Ïåðâûì (ïðåäâàðèòåëüíûì) ýòàïîì âñÿêîé ìèíèìèçàöèè ÿâëÿåò-
ñÿ âûäåëåíèå íåîïðåäåëåííûõ âûõîäíûõ ñèãíàëîâ è ñîñòîÿíèé è âíå-
ñåíèå ñîîòâåòñòâóþùåé íåîïðåäåëåííîñòè â òàáëèöû ïåðåõîäîâ è
âûõîäîâ àâòîìàòà òàêèì îáðàçîì, ÷òîáû íå èçìåíèòü îïåðàòîð àâ-
òîìàòà. Ñ ýòîé öåëüþ ïðè çàäàíèè ÷àñòè÷íîãî àâòîìàòà Ìèëè òàá-
ëèöàìè ïåðåõîäîâ è âûõîäîâ íóæíî ïðî÷åðêíóòü âñå ìåñòà â òàáëè-
öå ïåðåõîäîâ àâòîìàòà, êîòîðûì ñîîòâåòñòâóþò ïðî÷åðêíóòûå ìåñ-
òà â òàáëèöå âûõîäîâ. Åñëè äëÿ ÷àñòè÷íûõ àâòîìàòîâ Ìóðà ñ÷èòàòü
çàïðåùåííûìè ñîñòîÿíèÿ, äëÿ êîòîðûõ íå îïðåäåëåíà ôóíêöèÿ âûõî-
äîâ, òî â òàáëèöå ïåðåõîäîâ àâòîìàòà Ìóðà íóæíî çàìåíèòü ÷åðòî÷-
êàìè ñèìâîëû çàïðåùåííûõ ñîñòîÿíèé.
Страницы
- « первая
- ‹ предыдущая
- …
- 43
- 44
- 45
- 46
- 47
- …
- следующая ›
- последняя »
