Составители:
37
âåðøèíó a
j
ïðîâîäèòñÿ äóãà, îêîëî êîòîðîé â ÷èñëèòåëå óêàçûâàåòñÿ
âõîäíîé ñèãíàë, âûçûâàþùèé ýòîò ïåðåõîä, à â çíàìåíàòåëå âîçíèêà-
þùèé ïðè ýòîì âûõîäíîé ñèãíàë.
Äëÿ àâòîìàòà Ìóðà âåðøèíû ãðàôà îòìå÷àþòñÿ ñîñòîÿíèÿìè è ñâÿ-
çàííûìè ñ íèìè âõîäíûìè ñèãíàëàìè. Äóãè ãðàôà îòìå÷àþòñÿ âõîäíû-
ìè ñèãíàëàìè, ïîä äåéñòâèåì êîòîðûõ âîçíèêàþò ðàññìàòðèâàåìûå
ïåðåõîäû.
 ïðèâåäåííûõ ïðèìåðàõ ôóíêöèè δ è λ îïðåäåëåíû ïðè âñåõ çíà÷å-
íèÿõ ïåðåìåííûõ a(t1) è z(t), ïîýòîìó èì ñîîòâåòñòâóþò âïîëíå îïðå-
äåëåííûå àâòîìàòû. Äëÿ ÷àñòè÷íûõ àâòîìàòîâ ôóíêöèè δ è λ îïðåäå-
ëåíû íå íà âñåõ ïàðàõ a(t1) è z(t).  ýòîì ñëó÷àå íà ìåñòå íåîïðåäå-
ëåííûõ ïåðåõîäîâ èëè âûõîäîâ â òàáëèöàõ ñòàâÿòñÿ ïðî÷åðêè.  ãðàôàõ
æå îòñóòñòâóþò äóãè, ñîîòâåòñòâóþùèå íåîïðåäåëåííûì ïåðåõîäàì, à
âìåñòî íåîïðåäåëåííûõ âûõîäíûõ ñèãíàëîâ ñòàâÿòñÿ ïðî÷åðêè.
Åñëè çàäàíû ôóíêöèè ïåðåõîäîâ è âûõîäîâ àâòîìàòà, ïî íèì ìîæíî
ïîñòðîèòü îïåðàòîð àâòîìàòà. Îäíàêî íå ïî âñÿêîìó çàäàííîìó àëôàâèò-
íîìó îïåðàòîðó ìîæíî ïîñòðîèòü ôóíêöèè ïåðåõîäîâ è âûõîäîâ íåêîòîðî-
ãî àâòîìàòà.
4.4. Àâòîìàòíûå îïåðàòîðû
Ïóñòü îïåðàòîð j
A
àâòîìàòà A óäîâëåòâîðÿåò ñëåäóþùèì ÷åòûðåì
óñëîâèÿì.
1. ϕ
A
îñóùåñòâëÿåò îäíîçíà÷íîå îòîáðàæåíèå (âîîáùå ãîâîðÿ, ÷àñ-
òè÷íîå) ìíîæåñòâà âõîäíûõ ñëîâ â ìíîæåñòâî âûõîäíûõ ñëîâ.
2. Îáëàñòü îïðåäåëåíèÿ îïåðàòîðà ϕ
A
óäîâëåòâîðÿåò óñëîâèÿì ïîë-
íîòû, ò. å. âìåñòå ñ ëþáûì ñîäåðæàùèìñÿ â íåé ñëîâîì ñîäåðæèò è
âñå íà÷àëüíûå îòðåçêè ýòîãî ñëîâà (òàê, åñëè îáëàñòè îïðåäåëåíèÿ îïå-
ðàòîðà ϕ
A
ïðèíàäëåæèò ñëîâî z
1
z
2
z
3
z
4
, òî åé ïðèíàäëåæàò è ñëîâà z
1
, z
1
z
2
,
z
1
z
2
z
3
). Ïóñòîå ñëîâî âñåãäà âõîäèò â îáëàñòü îïðåäåëåíèÿ îïåðàòîðà
ϕ
A
.
3. ϕ
A
ñîõðàíÿåò äëèíó ñëîâà: ëþáîå âõîäíîå ñëîâî p, íà êîòîðîì îïå-
ðàòîð ϕ
A
îïðåäåëåí, èìååò òó æå äëèíó, ÷òî è åãî îáðàç ϕ
A
(p).  ÷àñòíî-
ñòè, ïóñòîå ñëîâî ïåðåâîäèòñÿ îïåðàòîðîì ϕ
A
â ïóñòîå ñëîâî.
4. ϕ
A
ïåðåâîäèò ëþáîé íà÷àëüíûé îòðåçîê ñëîâà p, íà êîòîðîì îí
îïðåäåëåí, â èìåþùèé òó æå äëèíó íà÷àëüíûé îòðåçîê ñëîâà ϕ
A
(p).
Ýòè ÷åòûðå óñëîâèÿ íàçûâàþò óñëîâèÿìè àâòîìàòíîñòè îïåðàòîðà,
à óäîâëåòâîðÿþùèé èì îïåðàòîð àâòîìàòíûì îïåðàòîðîì.
Страницы
- « первая
- ‹ предыдущая
- …
- 35
- 36
- 37
- 38
- 39
- …
- следующая ›
- последняя »
