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

UptoLike

ВУЗ: 

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

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

Рубрика: 

44
Âòîðîå îòëè÷èå â ÷èñëå íà÷àëüíûõ ñîñòîÿíèé. Òàê êàê ïîñëåäíÿÿ
áóêâà êàæäîãî âõîäíîãî ñëîâà äîëæíà ïåðåâîäèòü àâòîìàò â íà÷àëüíîå
ñîñòîÿíèå, ïîñëåäíÿÿ áóêâà êàæäîãî âûõîäíîãî ñëîâà ñîîòâåòñòâóåò
íà÷àëüíîìó ñîñòîÿíèþ. Ïîñêîëüêó âûõîäíûå ñëîâà â òàáë. 5.3 ñîäåð-
æàò äâå ðàçëè÷íûå ïîñëåäíèå áóêâû w
0
è w
1
, àâòîìàò äîëæåí èìåòü
äâà ðàâíîïðàâíûõ íà÷àëüíûõ ñîñòîÿíèÿ a
0
'
è a
1
'
, îòìå÷åííûõ âûõîäíûìè
ñèãíàëàìè w
0
è w
1
ñîîòâåòñòâåííî. Ýòè ñîñòîÿíèÿ äîëæíû áûòü ðàâíî-
ïðàâíûìè â òîì ñìûñëå, ÷òî ïðè z(1) = z
0
àâòîìàò èç êàæäîãî èç íèõ
ïåðåõîäèò â ñîñòîÿíèå a
1
, à ïðè z(1) = z
1
àâòîìàò èç êàæäîãî èç íèõ
ïåðåõîäèò â ñîñòîÿíèå a
12
.
Àâòîìàòû, ñîîòâåòñòâóþùèå ðèñ. 5.1 è 5.2, èìåþò âõîäíîé àëôàâèò
{z
0
, z
1
, a}. Òàê êàê èç êàæäîé âåðøèíû ýòèõ ãðàôîâ âûõîäÿò äóãè, îòìå-
÷åííûå íå áîëåå ÷åì äâóìÿ èç ýòèõ ñèìâîëîâ, ðàññìàòðèâàåìûå àâòî-
ìàòû áóäóò ÷àñòè÷íûìè.
Ïî ãðàôàì, èçîáðàæåííûì íà ðèñ. 5.1 è 5.2, ëåãêî ìîæíî ïîñòðî-
èòü òàáëèöû ïåðåõîäîâ è âûõîäîâ àâòîìàòîâ.
5.2. Ïîñòàíîâêà çàäà÷è î ñèíòåçå àâòîìàòîâ
Ñèíòåç àâòîìàòà çàêëþ÷àåòñÿ â ðåàëèçàöèè àâòîìàòà â âèäå óñò-
ðîéñòâà, ñîîòâåòñòâóþùåãî çàäàíèþ. Äëÿ êîíå÷íûõ àâòîìàòîâ çà-
äàíèåì îáû÷íî ñëóæèò ïðåäñòàâëåííûé â âèäå òàáëèöû ñîîòâåòñòâèÿ
àëôàâèòíûé îïåðàòîð. Ïðîöåññ ñèíòåçà ñîñòîèò èç äâóõ ýòàïîâ: ýòà-
ïà àáñòðàêòíîãî ñèíòåçà è ýòàïà ñòðóêòóðíîãî ñèíòåçà.
Íà ýòàïå àáñòðàêòíîãî ñèíòåçà âõîäíûå è âûõîäíûå ñèãíàëû
ðàññìàòðèâàþòñÿ ïðîñòî êàê áóêâû âõîäíîãî è âûõîäíîãî àëôàâè-
òîâ. Ïðè ðàññìîòðåíèè ñîñòîÿíèé èíòåðåñóþòñÿ èõ ÷èñëîì, ñ÷èòàÿ,
÷òî ïðè ìåíüøåì ÷èñëå ñîñòîÿíèé ðåàëèçàöèÿ àâòîìàòà ïðîùå. Ýòîò
ýòàï ñèíòåçà çàêëþ÷àåòñÿ â ïîñòðîåíèè ôóíêöèé ïåðåõîäîâ è âûõî-
äîâ àâòîìàòà ïî çàäàííîìó àëôàâèòíîìó îïåðàòîðó è â íàõîæäåíèè
àáñòðàêòíîãî àâòîìàòà ñ íàèìåíüøèì ÷èñëîì ñîñòîÿíèé â íåêîòî-
ðîì ñìûñëå ýêâèâàëåíòíîãî èñõîäíîìó.
Íà ýòàïå ñòðóêòóðíîãî ñèíòåçà âûáèðàåòñÿ ñïîñîá ïðåäñòàâ-
ëåíèÿ âõîäíûõ è âûõîäíûõ ñèãíàëîâ ÷åðåç ñèãíàëû, ïðèíÿòûå çà
ýëåìåíòàðíûå, à òàêæå ñïîñîá ïðåäñòàâëåíèÿ ñîñòîÿíèé àâòîìà-
òà ÷åðåç ñîñòîÿíèÿ àâòîìàòîâ, ïðèíÿòûõ çà ýëåìåíòàðíûå. Êî-
íå÷íîé öåëüþ ñòðóêòóðíîãî ñèíòåçà ÿâëÿåòñÿ ïîëó÷åíèå ñõåìû,

Страницы