Лупал А.М. Теория автоматов (часть 1)
Подождите немного. Документ загружается.
31
âòîðîé âûõîäíûì àëôàâèòîì äàííîãî îïåðàòîðà. Àëôàâèòíûé îïåðà-
òîð, ñîïîñòàâëÿþùèé êàæäîìó âõîäíîìó ñëîâó (ñëîâó âî âõîäíîì àëôà-
âèòå îïåðàòîðà) íå áîëåå îäíîãî âûõîäíîãî ñëîâà (ñëîâà â âûõîäíîì
àëôàâèòå îïåðàòîðà), íàçûâàþò îäíîçíà÷íûì. Åñëè àëôàâèòíûé îïåðà-
òîð íå ñîïîñòàâëÿåò äàííîìó âõîäíîìó ñëîâó íèêàêîãî âûõîäíîãî ñëîâà
(â òîì ÷èñëå è ïóñòîãî), òî ãîâîðÿò, ÷òî îí íå îïðåäåëåí íà ýòîì ñëîâå.
Ñîâîêóïíîñòü âñåõ ñëîâ, íà êîòîðûõ àëôàâèòíûé îïåðàòîð îïðåäåëåí,
íàçûâàåòñÿ åãî îáëàñòüþ îïðåäåëåíèÿ. Àëôàâèòíûé îïåðàòîð íàçûâàþò
÷àñòè÷íûì, åñëè åãî îáëàñòü îïðåäåëåíèÿ íå ñîâïàäàåò ñ ñîâîêóïíîñòüþ
âñåõ âõîäíûõ ñëîâ.
Âñÿêèé äèñêðåòíûé ïðåîáðàçîâàòåëü èíôîðìàöèè, âûäàþùèé íåêîòî-
ðûé âûõîäíîé ñèãíàë (áóêâó âûõîäíîãî àëôàâèòà) â îòâåò íà êàæäûé
âõîäíîé ñèãíàë (áóêâó âõîäíîãî àëôàâèòà), ðåàëèçóåò íåêîòîðûé àëôà-
âèòíûé îïåðàòîð. Òàêèå ïðåîáðàçîâàòåëè âîñïðèíèìàþò è âûäàþò ñèãíà-
ëû ëèøü â ìîìåíòû âðåìåíè, ðàçäåëåííûå ïðîìåæóòêàìè íåíóëåâîé
äëèòåëüíîñòè, è íàçûâàþòñÿ àâòîìàòàìè.
 îáùåì ñëó÷àå âûõîäíîé ñèãíàë àâòîìàòà â êàæäûé ìîìåíò âðå-
ìåíè çàâèñèò îò çíà÷åíèé âõîäíîãî ñèãíàëà íå òîëüêî â äàííûé, íî è â
ïðåäûäóùèå ìîìåíòû âðåìåíè. Ýòà çàâèñèìîñòü ïðîÿâëÿåòñÿ â èçìå-
íåíèè ó àâòîìàòà åãî âíóòðåííèõ ñîñòîÿíèé òàêèì îáðàçîì, ÷òî ñèãíàë
íà åãî âûõîäå â êàæäûé ìîìåíò âðåìåíè îïðåäåëÿåòñÿ êàê âõîäíûì
ñèãíàëîì â òîò æå ìîìåíò âðåìåíè, òàê è ñîñòîÿíèåì, â êîòîðîì îêà-
çàëñÿ àâòîìàò ê äàííîìó ìîìåíòó âðåìåíè â ðåçóëüòàòå âîçäåéñòâèÿ
íà åãî âõîä ñèãíàëîâ, ïîñòóïèâøèõ â ïðåäûäóùèå ìîìåíòû âðåìåíè.
Åñëè âûõîäíîé ñèãíàë àâòîìàòà â êàæäûé ìîìåíò âðåìåíè öåëèêîì
îïðåäåëÿåòñÿ âõîäíûì ñèãíàëîì â òîò æå ìîìåíò âðåìåíè, òî àâòîìàò
èìååò åäèíñòâåííîå âíóòðåííåå ñîñòîÿíèå è åãî íàçûâàþò êîìáè-
íàöèîííîé ñõåìîé.
Ïðèìåðîì àâòîìàòà ñ íååäèíñòâåííûì ñîñòîÿíèåì ìîæåò ñëóæèòü
óñòðîéñòâî óïðàâëåíèÿ ëèôòîì. Âõîäíûìè ñèãíàëàìè äëÿ íåãî ÿâëÿþò-
ñÿ íîìåðà òðåáóåìûõ ýòàæåé Z
1
< Z
2
< ... < Z
F
< ∞. Ðåàêöèÿ êàáèíû
ëèôòà íà êàæäûé âõîäíîé ñèãíàë äîëæíà áûòü ðàçëè÷íîé â çàâèñèìîñ-
òè îò òîãî, íà êàêîé ýòàæ êàáèíà ïðèâåäåíà âõîäíûìè ñèãíàëàìè, ïîñòó-
ïèâøèìè ê äàííîìó ìîìåíòó âðåìåíè. Åñëè êàáèíà íàõîäèòñÿ íèæå
òðåáóåìîãî ýòàæà îíà äîëæíà äâèãàòüñÿ ââåðõ äî òðåáóåìîãî ýòàæà,
åñëè âûøå âíèç äî òðåáóåìîãî ýòàæà, åñëè íà òðåáóåìîì ýòàæå
äîëæíà îñòàòüñÿ íà ìåñòå. Òàêèì îáðàçîì, âûõîäíûå ñèãíàëû w
j
óñò-
32
ðîéñòâà óïðàâëåíèÿ ëèôòîì ìîæíî ñ÷èòàòü ðàâíûìè ðàçíîñòÿì z
i
z
k
,
ãäå z
k
íîìåð ýòàæà, íà êîòîðîì íàõîäèëàñü êàáèíà ëèôòà ê ìîìåíòó
ïîñòóïëåíèÿ î÷åðåäíîãî âõîäíîãî ñèãíàëà (íîìåðà òðåáóåìîãî ýòàæà)
z
i
, ïðè ýòîì ñèãíàë w
j
= 0 íå âêëþ÷àåòñÿ â âûõîäíîé àëôàâèò (ïóñòîé
ñèìâîë). Ïîÿâëåíèå êàæäîãî âûõîäíîãî ñèãíàëà çàâèñèò îò âõîäíîãî
ñèãíàëà, äåéñòâóþùåãî â äàííûé ìîìåíò âðåìåíè, è îò íîìåðà ýòàæà,
íà êîòîðîì ê ýòîìó ìîìåíòó âðåìåíè îêàçàëàñü êàáèíà ëèôòà. Ïî ýòîé
ïðè÷èíå ìîæíî ñ÷èòàòü, ÷òî àâòîìàò óïðàâëåíèÿ ëèôòîì èìååò ÷èñëî
ñîñòîÿíèé, ðàâíîå ÷èñëó ýòàæåé çäàíèÿ. Ïîñêîëüêó ïðîöåññ äâèæåíèÿ
êàáèíû ìåæäó ýòàæàìè íå ïðåäñòàâëÿåò èíòåðåñà, ñ÷èòàåòñÿ, ÷òî ñî-
ñòîÿíèå àâòîìàòà èçìåíÿåòñÿ ìãíîâåííî â ìîìåíò äîñòèæåíèÿ êàáè-
íîé î÷åðåäíîãî ýòàæà è ñ ýòèì æå ìîìåíòîì âðåìåíè îòîæäåñòâëÿåòñÿ
ìîìåíò ïîñòóïëåíèÿ âõîäíîãî ñèãíàëà, âûçâàâøåãî äâèæåíèå êàáèíû ê
ýòîìó ýòàæó.
4.2. Àáñòðàêòíûå àâòîìàòû
Àâòîìàòû, ðàññìàòðèâàåìûå áåçîòíîñèòåëüíî ê èõ âíóòðåííåé ñòðóê-
òóðå, ïðèíÿòî íàçûâàòü àáñòðàêòíûìè àâòîìàòàìè.
Àáñòðàêòíûé àâòîìàò ðàáîòàåò â äèñêðåòíîì àâòîìàòíîì âðåìåíè,
ïîñëåäîâàòåëüíûå ìîìåíòû êîòîðîãî îòîæäåñòâëÿþòñÿ ñ íàòóðàëüíû-
ìè ÷èñëàìè t= 1, 2, ... .  ïðèìåðå ñ ëèôòîì ìîìåíòû àâòîìàòíîãî
âðåìåíè îïðåäåëÿþòñÿ êíîïêîé ïóñê ëèáî ìîìåíòàìè íàæàòèÿ êíî-
ïîê ñ íîìåðàìè òðåáóåìûõ ýòàæåé.
Äëÿ çàäàíèÿ àáñòðàêòíîãî àâòîìàòà íóæíî çàäàòü âõîäíîé àëôà-
âèò Z = {z
1
, z
2
, ..., z
F
}, âûõîäíîé àëôàâèò W = {w
1
, w
2
, ..., w
G
} è
ìíîæåñòâî A = {a
1
, a
2
, ..., a
M
} åãî âíóòðåííèõ ñîñòîÿíèé, íàçûâàåìîå
ïðîñòî ìíîæåñòâîì ñîñòîÿíèè àâòîìàòà. Â êàæäûé ìîìåíò âðåìåíè
t = 0, 1, 2, ... àáñòðàêòíûé àâòîìàò A íàõîäèòñÿ â íåêîòîðîì ñîñòîÿ-
íèè a
i
= a(t) èç A. Ñîñòîÿíèå a
0
= a(0) â íà÷àëüíûé ìîìåíò âðåìåíè t = 0
íàçûâàåòñÿ íà÷àëüíûì ñîñòîÿíèåì àâòîìàòà A. Óñëîâíî àáñòðàêòíûé
àâòîìàò èçîáðàæàåòñÿ â âèäå óñòðîéñòâà (ðèñ. 4.1) ñ îäíèì âõîäîì è
îäíèì âûõîäîì.
A = {a
, a
, ..., a
M
}
Z = {z
, z
, ..., z
F
} W = {w
, w
, ..., w
G
}
Ðèñ. 4.1
33
 êàæäûé ìîìåíò t àâòîìàòíîãî âðåìåíè, íà÷èíàÿ c t = 1, íà âõîä
àâòîìàòà ïîñòóïàåò â êà÷åñòâå âõîäíîãî ñèãíàëà îäíà èç áóêâ z
i
= z(t)
àëôàâèòà Z. Êîíå÷íûå óïîðÿäî÷åííûå ïîñëåäîâàòåëüíîñòè âõîäíûõ áóêâ
z(1)z(2)...z(k) àâòîìàòà áóäóò âõîäíûìè ñëîâàìè. Íà âõîä àâòîìàòà
ìîæåò ïîäàâàòüñÿ ëþáîå âõîäíîå ñëîâî èç íåêîòîðîãî ôèêñè-
ðîâàííîãî ìíîæåñòâà äîïóñòèìûõ âõîäíûõ ñëîâ. Êàæäîå äîïóñòèìîå
ñëîâî p = z(1)z(2)...z(k), ïîäàííîå íà âõîä äàííîãî àâòîìàòà A, âûçûâà-
åò ïîÿâëåíèå íà âûõîäå àâòîìàòà âûõîäíîãî ñëîâà q = w(1)w(2)...w(k),
ïðåäñòàâëÿþùåãî ñîáîé íåêîòîðóþ óïîðÿäî÷åííóþ êîíå÷íóþ ïîñëåäî-
âàòåëüíîñòü âûõîäíûõ ñèãíàëîâ àâòîìàòà A (áóêâ àëôàâèòà W), èìåþ-
ùåãî òó æå ñàìóþ äëèíó, ÷òî è ñîîòâåòñòâóþùåå åìó âõîäíîå ñëîâî p.
Ïîëó÷àåìîå ïðåîáðàçîâàíèå ϕ
A
äîïóñòèìûõ âõîäíûõ ñëîâ p â
ñîîòâåòñòâóþùèå èì âûõîäíûå ñëîâà q ÿâëÿåòñÿ àëôàâèòíûì îïåðàòî-
ðîì, èíäóöèðîâàííûì àâòîìàòîì A, èëè ïðîñòî îïåðàòîðîì àâòîìàòà A.
 ïðèìåðå ñ ëèôòîì îïåðàòîð óïðàâëÿþùåãî àâòîìàòà ìîæíî çà-
äàòü ÿâíî. Èç íàéäåííûõ âûøå ñîîòíîøåíèé ìåæäó âõîäíûìè è âûõîä-
íûìè ñèãíàëàìè äëÿ ýòîãî àâòîìàòà ñëåäóåò, ÷òî
w(t) = z(t) z(t1),
åñëè ïðèíÿòü z(0) = z
1
. Ýòî è åñòü èñêîìîå ïðåîáðàçîâàíèå âõîäíûõ ñëîâ
àâòîìàòà â âûõîäíûå. Ïîñêîëüêó äëèíà âõîäíûõ ñëîâ äëÿ ýòîãî ïðåîáðà-
çîâàíèÿ íå îãðàíè÷åíà, ìíîæåñòâî äîïóñòèìûõ âõîäíûõ ñëîâ äëÿ íåãî
áåñêîíå÷íî è äàæå íåñ÷åòíî ïðè âñÿêîì F
≥ 2.
Îïåðàòîð ϕ
A
îäíîçíà÷íî îïðåäåëÿåòñÿ çàäàíèåì ôóíêöèè ïåðåõîäîâ
δ è ôóíêöèè âûõîäîâ λ ðàññìàòðèâàåìîãî àâòîìàòà. Ôóíêöèÿ ïåðåõî-
äîâ îïðåäåëÿåò ñîñòîÿíèå a(t) àâòîìàòà â íåêîòîðûé ìîìåíò t àâòî-
ìàòíîãî âðåìåíè ïî âõîäíîìó ñèãíàëó z(t) â òîò æå ñàìûé ìîìåíò è
ñîñòîÿíèé a(t1) â ïðåäûäóùèé ìîìåíò àâòîìàòíîãî âðåìåíè
a(t) = δ(a(t1), z(t)). (4.1)
Ôóíêöèÿ âûõîäîâ îïðåäåëÿåò çàâèñèìîñòü âûõîäíîãî ñèãíàëà îò òåõ
æå ñàìûõ ïåðåìåííûõ
w(t) = λ(a(t1), z(t)). (4.2)
Çàäàâàÿ ëþáîå âûõîäíîå ñëîâî p = z(1)z(2)...z(k) è íà÷àëüíîå ñîñòîÿ-
íèå a(0) àâòîìàòà, ñ ïîìîùüþ ñîîòíîøåíèé (4.1) è (4.2) ìîæíî ïîñ-
ëåäîâàòåëüíî îïðåäåëèòü âñå áóêâû ñîîòâåòñòâóþùåãî âûõîäíîãî ñëî-
âà
q = ϕ
A
(p) = w(1)w(2)...w(k).
34
Òàêèì îáðàçîì, ñîîòíîøåíèÿ (4.1) è (4.2) äåéñòâèòåëüíî îïðåäåëÿ-
þò îïåðàòîð ϕ
A
àâòîìàòà A.
Ôóíêöèè ïåðåõîäîâ è âûõîäîâ ïðåäñòàâëÿþòñÿ îáû÷íî àáñòðàêòíû-
ìè ÷àñòè÷íûìè ôóíêöèÿìè δ(a, z) è λ(a, z), çàäàþùèìè îäíîçíà÷íîå
îòîáðàæåíèå íåêîòîðîãî ìíîæåñòâà ïàð (a, z)(a∈A, z∈Z) â ìíîæåñòâà
A è W ñîîòâåòñòâåííî. Äîïóñòèìûìè âõîäíûìè ñëîâàìè äëÿ àâòîìàòà
A íàçûâàþò òå è òîëüêî òå âõîäíûå ñëîâà p, íà êîòîðûõ ñ ïîìîùüþ
ôóíêöèé δ è λ óêàçàííûì âûøå ñïîñîáîì ìîæíî îïðåäåëèòü ñîîòâåò-
ñòâóþùèå èì âûõîäíûå ñëîâà q = ϕ
A
(p).
Àâòîìàò íàçûâàþò êîíå÷íûì, åñëè êîíå÷íû âñå òðè îïðåäåëÿþùèå
åãî ìíîæåñòâà Z, W, A.
Äëÿ ïðèìåðà ñ ëèôòîì ôóíêöèè ïåðåõîäîâ è âûõîäîâ îïðåäåëÿþòñÿ
ñîîòâåòñòâåííî ñëåäóþùèìè ðàâåíñòâàìè:
a(t) = z(t),
w(t) = z(t)a(t1).
Àâòîìàò óïðàâëåíèÿ ëèôòîì êîíå÷åí, õîòÿ îáëàñòü îïðåäåëåíèÿ åãî
îïåðàòîðà ñîñòîèò èç áåñêîíå÷íîãî ìíîæåñòâà äîïóñòèìûõ ñëîâ.
Ïîñêîëüêó äàëüøå áóäóò ðàññìàòðèâàòüñÿ òîëüêî êîíå÷íûå àâòîìà-
òû, ñëîâî êîíå÷íûé áóäåò îïóñêàòüñÿ.
Àâòîìàò íàçûâàþò âïîëíå îïðåäåëåííûì, åñëè åãî ôóíêöèè ïåðåõî-
äîâ è âûõîäîâ çàäàíû íà âñåõ ïàðàõ (a, z), è ÷àñòè÷íûì â ïðîòèâíîì
ñëó÷àå.
Äâà àáñòðàêòíûõ àâòîìàòà ñ÷èòàþòñÿ îäèíàêîâûìè, åñëè îíè îòëè-
÷àþòñÿ äðóã îò äðóãà ëèøü îáîçíà÷åíèÿìè âõîäíûõ è âûõîäíûõ ñèãíà-
ëîâ, ñîñòîÿíèé.
4.3. Ñïîñîáû çàäàíèÿ àáñòðàêòíûõ àâòîìàòîâ
Åñëè çàäàíû âõîäíîé è âûõîäíîé àëôàâèòû àâòîìàòà, à òàêæå ìíî-
æåñòâî åãî ñîñòîÿíèé, ñðåäè êîòîðûõ ôèêñèðîâàíî íà÷àëüíîå ñîñòîÿ-
íèå a
0
, äëÿ çàäàíèÿ àáñòðàêòíîãî àâòîìàòà îñòàåòñÿ çàäàòü ôóíêöèþ
ïåðåõîäîâ δ ôóíêöèþ âûõîäîâ A .
Àâòîìàòû, ôóíêöèè ïåðåõîäîâ è âûõîäîâ êîòîðûõ óäîâëåòâîðÿþò
óñëîâèÿì (4.1), (4.2), íàçûâàþò àâòîìàòàìè Ìèëè. Àâòîìàòû, ó êîòî-
ðûõ ôóíêöèè ïåðåõîäîâ è âûõîäîâ óäîâëåòâîðÿþò óñëîâèÿì
a(t) = δ(a(t1), z(t)), (4.3)
35
w(t) = λ(a(t)), (4.4)
íàçûâàþò àâòîìàòàìè Ìóðà [2] .
Ðàçëè÷èå ìåæäó àâòîìàòàìè Ìèëè è Ìóðà ñîñòîèò â òîì, ÷òî âû-
õîäíîé ñèãíàë â àâòîìàòå Ìèëè çàâèñèò êàê îò ñîñòîÿíèÿ â ïðåäûäó-
ùèé ìîìåíò âðåìåíè, òàê è îò âõîäíîãî ñèãíàëà â ðàññìàòðèâàåìûé
ìîìåíò âðåìåíè, à â àâòîìàòå Ìóðà òîëüêî îò ñîñòîÿíèÿ â ðàññìàò-
ðèâàåìûé ìîìåíò âðåìåíè. Åñëè ïîäñòàâèòü ïðàâóþ ÷àñòü (4.3) â (4.4),
òî ïîëó÷èòñÿ ðàâåíñòâî òèïà (4.2). Òàêèì îáðàçîì, àâòîìàò Ìóðà âñå-
ãäà ìîæíî ñâåñòè ê àâòîìàòó Ìèëè ñ òåì æå ñàìûì ÷èñëîì ñîñòîÿíèé
è òåìè æå ñàìûìè âõîäíûì è âûõîäíûì àëôàâèòàìè. Äëÿ êîíå÷íîãî
àâòîìàòà ôóíêöèè δ è λ îïðåäåëåíû íà êîíå÷íîì ìíîæåñòâå çíà÷åíèé
àðãóìåíòîâ è ïðèíèìàþò çíà÷åíèÿ èç êîíå÷íûõ ìíîæåñòâ. Ïî ýòîé ïðè-
÷èíå äëÿ êîíå÷íûõ àâòîìàòîâ ôóíêöèè δ è λ ìîæíî çàäàòü â âèäå òàá-
ëèö.
Òàáëèöà 4.1 Òàáëèöà 4.2
 òàáë. 4.1 è 4.2 ïðèâåäåíû ïðèìåðû ñîîòâåòñòâåííî ôóíêöèé ïåðå-
õîäîâ è âûõîäîâ àâòîìàòà Ìèëè.
Ïîñêîëüêó îáëàñòè îïðåäåëåíèÿ ôóíêöèé δ è λ ñîâïàäàþò, òàáëèöû
ïåðåõîäîâ è âûõîäîâ ìîãóò áûòü ñîâìåùåíû â îäíó òàáëèöó ïåðåõîäîâ-
âûõîäîâ (òàáë. 4.3), â êîòîðîé íà ïåðåñå÷åíèè i-é ñòðîêè è j-ãî ñòîëáöà
(i∈{0, 1, 2, ..., n}, j∈{0, 1, 2, ..., r}) çàïèñûâàåòñÿ â ÷èñëèòåëå íîâîå
ñîñòîÿíèå àâòîìàòà, à â çíàìåíàòåëå âûõîäíîé ñèãíàë, âûðàáîòàííûé
ïðè ïåðåõîäå â ýòî ñîñòîÿíèå.
 òàáë. 4.4, 4.5 ïðèâåäåíû ïðèìåðû ôóíêöèé ïåðåõîäîâ δ è âûõîäîâ
λ àâòîìàòà Ìóðà. Ôóíêöèÿ âûõîäîâ λ àâòîìàòà Ìóðà çàâèñèò òîëüêî îò
îäíîãî ïàðàìåòðà à(t), ïîýòîìó ïðè ñîâìåùåíèè òàáëèö ïåðåõîäîâ è
âûõîäîâ äîñòàòî÷íî ñòîëáöó ñîñòîÿíèé àâòîìàòà ïîñòàâèòü â ñîîòâåò-
ñòâèå ñòîëáåö âûõîäíûõ ñèãíàëîâ (òàáë. 4.6).
at ` z
z
z
a
a
a
!
a
a
a
!
a
a
a
a
a
a
a
!
a
a
a
!
a t z
z
z
a
w
!
w
w
a
w
0
w
!
w
a
w
w
w
a
3
w
w
w
!
36
Òàáëèöà 4.3 Òàáëèöà 4.4
Òàáëèöà 4.5 Òàáëèöà 4.6
Âîçìîæåí ãðàôè÷åñêèé ñïîñîá çàäàíèÿ ôóíêöèé ïåðåõîäîâ è âûõî-
äîâ àâòîìàòà. Íà ðèñ. 4.2 è 4.3 ïðèâåäåíû ãðàôû ïåðåõîäîâ àâòîìàòîâ
Ìèëè è Ìóðà, òàáëèöû ïåðåõîäîâ-âûõîäîâ êîòîðûõ òîëüêî ÷òî ðàññìàò-
ðèâàëèñü.
Äëÿ àâòîìàòà Ìèëè âåðøèíû ãðàôà îòìå÷àþòñÿ ñîñòîÿíèÿìè. Åñëè
èç ñîñòîÿíèÿ a
i
èìååòñÿ ïåðåõîä â ñîñòîÿíèå a
j
, òî èç âåðøèíû a
i
â
w t at ` z
z
z
w
a
a
!
a
a
w
a
a
a
!
a
w
!
a
a
a
a
w
a
3
a
a
a
at wt
a
w
a
w
a
w
!
a
3
w
a t z
z
z
a
a
!
a
a
a
a
a
!
a
a
a
a
a
a
3
a
a
a
a t z
z
z
a
a
w/
!
a
!
w/
a
w/
a
a
!
w/
a
w/
!
a
w/
0
a
a
w/
a
w/
a
w/
2
a
3
a
w/
a
w/
a
!
w/
!
a
0
a
1
a
2
a
3
z
z
z
z
/
/
/
/
w
w
w
w
1
2
1
1
0
0
1
2
z
/
w
2
3
z
/
w
0
1
z
/
w
1
3
z
/
w
2
1
z
/
w
0
2
z
z
z
/
/
/
w
w
w
0
0
2
0
3
2
z
1
z
1
z
1
z
1
z
1
z
2
z
2
z
2
z
2
z
0
z
0
z
0
a
0
w
2
a
1
w
0
a
2
a
3
w
3
w
1
Ðèñ. 4.2 Ðèñ. 4.3
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).
Ýòè ÷åòûðå óñëîâèÿ íàçûâàþò óñëîâèÿìè àâòîìàòíîñòè îïåðàòîðà,
à óäîâëåòâîðÿþùèé èì îïåðàòîð àâòîìàòíûì îïåðàòîðîì.
38
Åñëè àëôàâèòíûé îïåðàòîð ϕ óäîâëåòâîðÿåò óñëîâèÿì àâòîìàòíî-
ñòè, ìîæíî ïîñòðîèòü àâòîìàòû Ìèëè è Ìóðà (âîîáùå ãîâîðÿ, áåñêîíå÷-
íûå), èíäóöèðóþùèå îïåðàòîð ϕ.  ñëó÷àå, êîãäà îáëàñòü îïðåäåëåíèÿ
îïåðàòîðà ϕ êîíå÷íà (êîíå÷íî ìíîæåñòâî ñëîâ, íà êîòîðûõ îïðåäåëåí
îïåðàòîð ϕ), ýòè àâòîìàòû òàêæå ìîãóò áûòü âûáðàíû êîíå÷íûìè [2] .
Íå âñÿêèé àëôàâèòíûé îïåðàòîð óäîâëåòâîðÿåò óñëîâèÿì àâòîìàò-
íîñòè. Ñóùåñòâóåò, îäíàêî, ïðèåì, ïîçâîëÿþùèé ïðåâðàòèòü ëþáîé àë-
ôàâèòíûé îïåðàòîð â àâòîìàòíûé îïåðàòîð.
Ïóñòü ϕ ïðîèçâîëüíûé àëôàâèòíûé îïåðàòîð ñ êîíå÷íûìè âõîä-
íûì Z è âûõîäíûì W àëôàâèòàìè, P îáëàñòü îïðåäåëåíèÿ ýòîãî îïå-
ðàòîðà. Áóäåì ïðèìåíÿòü ê îïåðàòîðó ϕ äâå îïåðàöèè. Ïåðâàÿ èç íèõ
íàçûâàåòñÿ îïåðàöèåé âûðàâíèâàíèÿ äëèí ñëîâ. Îíà çàêëþ÷àåòñÿ â òîì,
÷òî âî âõîäíîé è âûõîäíîé àëôàâèòû äîáàâëÿåòñÿ ïî îäíîé ïóñòîé áóê-
âå a è β ñîîòâåòñòâåííî, à çàòåì ê ëþáîìó ñëîâó p èç P ïðèïèñûâàþòñÿ
ñïðàâà m
p
ýêçåìïëÿðîâ áóêâû a, à ê åãî îáðàçó q = ϕ(p) ïðèïèñûâàþòñÿ
ñëåâà n
q
ýêçåìïëÿðîâ áóêâû β òàê, ÷òîáû äëèíû ïîëó÷åííûõ â ðåçóëü-
òàòå ïðèïèñûâàíèÿ ýòèõ áóêâ ñëîâ p
1
è q
1
ñîâïàëè. Åñëè, â ÷àñòíîñòè,
÷èñëà m
p
âûáèðàþòñÿ ðàâíûìè äëèíå ñëîâà q, à ÷èñëà n
q
ðàâíûìè äëè-
íå ñëîâà p, òî îïåðàöèÿ âûðàâíèâàíèÿ äëèíû ñëîâ íàçûâàåòñÿ ñòàí-
äàðòíîé.
Ïîñëå âûïîëíåíèÿ îïåðàöèè âûðàâíèâàíèÿ äëèí ñëîâ ñòðîèòñÿ íî-
âûé îïåðàòîð ϕ
1
, îòîáðàæàþùèé íåêîòîðîå ìíîæåñòâî P
1
ñëîâ â àëôà-
âèòå Z ∪ {a} â ìíîæåñòâî ñëîâ â àëôàâèòå W ∪ {β}. Îí äåéñòâóåò ïî
ïðàâèëó q
1
= ϕ
1
(p
1
), ãäå ñëîâà p
1
è q
1
ïîëó÷åíû âûðàâíèâàíèåì äëèí
ñëîâ p è q, ïðè÷åì p ïðîáåãàåò âñå P. Îïåðàòîð ϕ
1
íàçûâàåòñÿ ïðè ýòîì
âûðàâíåííûì îïåðàòîðîì.
Âòîðàÿ îïåðàöèÿ ïðèìåíÿåòñÿ òîëüêî ê âûðàâíåííûì àëôàâèòíûì
îïåðàòîðàì, ò. å. ê òàêèì îïåðàòîðàì, ó êîòîðûõ äëèíû âõîäíûõ è ñîîò-
âåòñòâóþùèõ èì âûõîäíûõ ñëîâ ðàâíû ìåæäó ñîáîé. Åå íàçûâàþò îïå-
ðàöèåé ïîïîëíåíèÿ. Îíà çàêëþ÷àåòñÿ â ðàñïðîñòðàíåíèè îòîáðàæåíèÿ
ϕ íà íà÷àëüíûå îòðåçêè ñëîâ. Ýòî îñóùåñòâëÿåòñÿ ñëåäóþùèì îáðà-
çîì. Åñëè S ïðîèçâîëüíûé íà÷àëüíûé îòðåçîê ëþáîãî ñëîâà p èç îáëà-
ñòè îïðåäåëåíèÿ îïåðàòîðà ϕ, òî ϕ(S) ïîëàãàåòñÿ ðàâíûì íà÷àëüíîìó
îòðåçêó ñëîâà ϕ(p), èìåþùèì òó æå, ÷òî è îòðåçîê S, äëèíó.
 ðåçóëüòàòå ïðèìåíåíèÿ îïåðàöèè ïîïîëíåíèÿ ê ïðîèçâîëüíîìó âû-
ðàâíåííîìó àëôàâèòíîìó îïåðàòîðó ϕ
1
âîçíèêàåò îïåðàòîð ϕ
1
'
, íàçûâà-
åìûé ïîïîëíåíèåì îïåðàòîðà ϕ
1
. Åñëè ïîïîëíåíèå ϕ
1
'
îïåðàòîðà ϕ
1
ÿâ-
39
ëÿåòñÿ îäíîçíà÷íûì, òî îíî óäîâëåòâîðÿåò, î÷åâèäíî, âñåì ÷åòûðåì óñ-
ëîâèÿì àâòîìàòíîñòè. Ê ñîæàëåíèþ, îäíàêî, â áîëüøèíñòâå ñëó÷àåâ
ïîïîëíåíèå îïåðàòîðà ϕ
1
íåîäíîçíà÷íî. Âìåñòå ñ òåì ñïðàâåäëèâî ñëå-
äóþùåå óòâåðæäåíèå [2]: â ñëó÷àå, êîãäà îïåðàòîð ϕ
1
ïîëó÷åí èç íåêî-
òîðîãî îäíîçíà÷íîãî àëôàâèòíîãî îïåðàòîðà â ðåçóëüòàòå ñòàíäàðòíîé
îïåðàöèè âûðàâíèâàíèÿ äëèí ñëîâ, ïîïîëíåíèå ϕ
1
'
ýòîãî îïåðàòîðà îä-
íîçíà÷íî è ÿâëÿåòñÿ àâòîìàòíûì îïåðàòîðîì.
 ðÿäå ñëó÷àåâ ïðè ïðåâðàùåíèè çàäàííîãî îïåðàòîðà â àâòîìàòíûé
îïåðàòîð ìîæíî ïðèìåíÿòü íå ñòàíäàðòíóþ îïåðàöèþ âûðàâíèâàíèÿ, à
êàêîé-íèáóäü áîëåå ýêîíîìíûé (ñ òî÷êè çðåíèÿ ÷èñëà äîïèñûâàåìûõ
áóêâ) âàðèàíò îïåðàöèè âûðàâíèâàíèÿ.  ÷àñòíîñòè, åñëè ñàì èñõîäíûé
îïåðàòîð áûë àâòîìàòíûì, ìîæíî ñ÷èòàòü, ÷òî ïðèìåíÿåòñÿ íóëåâàÿ
îïåðàöèÿ âûðàâíèâàíèÿ, ïðè êîòîðîé íèêàêîãî äîïèñûâàíèÿ ïóñòûõ áóêâ
âîîáùå íå ïðîèñõîäèò.
Îáû÷íî íà ïðàêòèêå ïîñòóïàþò ñëåäóþùèì îáðàçîì. Ñíà÷àëà îïåðà-
öèþ âûðàâíèâàíèÿ ïðîâîäÿò íàèáîëåå ýêîíîìíûì îáðàçîì, è, ïðèìåíÿÿ
çàòåì îïåðàöèþ ïîïîëíåíèÿ, ïðîâåðÿþò (ïî ïðèçíàêó îäíîçíà÷íîñòè
ïîïîëíåíèÿ), ïîëó÷èòñÿ ëè â ðåçóëüòàòå àâòîìàòíûé îïåðàòîð. Åñëè íåò,
òî ïðîèçâîäÿò íîâîå äîïèñûâàíèå ïóñòûõ áóêâ, íîâóþ ïðîâåðêó ïî-
ïîëíåíèÿ è ò.ä. Â ðåçóëüòàòå ïðîäîëæåíèÿ ïîäîáíîãî ïðîöåññà îáÿçà-
òåëüíî áóäåò ïîëó÷åí àâòîìàòíûé îïåðàòîð. Ýòîò ìåòîä ïðèâåäåíèÿ
àëôàâèòíîãî îïåðàòîðà ê àâòîìàòíîìó îïåðàòîðó íàçûâàþò ìåòîäîì
ïîñëåäîâàòåëüíîãî ïðèâåäåíèÿ.
Äëÿ ïîñòðîåííîãî òàêèì ìåòîäîì îïåðàòîðà ìîæíî ïîñòðîèòü ôóíê-
öèè ïåðåõîäîâ è âûõîäîâ.
40
5. ÀÁÑÒÐÀÊÒÍÛÉ ÑÈÍÒÅÇ ÀÂÒÎÌÀÒÎÂ
5.1. Ïîñòðîåíèå ôóíêöèé ïåðåõîäîâ è âûõîäîâ
ïî àëôàâèòíîìó îïåðàòîðó
Åñëè îáëàñòü îïðåäåëåíèÿ àëôàâèòíîãî îïåðàòîðà ϕ êîíå÷íà, åãî
÷àùå âñåãî çàäàþò ñ ïîìîùüþ òàáëèöû ñîîòâåòñòâèÿ.  ëåâîé ïîëîâè-
íå ýòîé òàáëèöû âûïèñûâàþò â òîì èëè èíîì ïîðÿäêå âõîäíûå ñëîâà,
íà êîòîðûõ çàäàí îïåðàòîð ϕ, à â ïðàâîé ÷àñòè òàáëèöû ñîîòâåòñòâó-
þùèå èì âûõîäíûå ñëîâà.
Ðàññìîòðèì ïðîöåññ ïîñòðîåíèÿ ôóíêöèé ïåðåõîäîâ è âûõîäîâ ïî
àëôàâèòíîìó îïåðàòîðó íà êîíêðåòíîì ïðèìåðå. Ïóñòü âõîäíîé è âû-
õîäíîé àëôàâèòû ñîñòîÿò òîëüêî èç äâóõ áóêâ {z
0
, z
1
} è {w
0
, w
1
} ñî-
îòâåòñòâåííî, à îïåðàòîð (òàáë. 5.1) çàäàí òàáëèöåé ñîîòâåòñòâèÿ.
Òàáëèöà 5.1
Äàííûé îïåðàòîð óæå âûðàâíåí, òàê êàê äëèíà êàæäîãî èç âõîäíûõ
ñëîâ ðàâíà äëèíå ñîîòâåòñòâóþùåãî âûõîäíîãî ñëîâà. Êàæäîìó âõîäíîìó
ñëîâó çäåñü ñîïîñòàâëÿåòñÿ íå áîëåå îäíîãî âûõîäíîãî ñëîâà, ïîýòîìó
îïåðàòîð ϕ îäíîçíà÷åí. Îäíàêî îí íå óäîâëåòâîðÿåò âòîðîìó óñëîâèþ
àâòîìàòíîñòè. Äåéñòâèòåëüíî, åñëè íóìåðîâàòü ñëîâà â òàáë. 5.1 ñâåðõó
âíèç, òî z(1) = z
0
äëÿ ïåðâîãî è òðåòüåãî ñëîâ ïðåîáðàçóåòñÿ â w(1) = w
1
,
à äëÿ âòîðîãî è ÷åòâåðòîãî ñëîâ w
1
(1) = w
0
. Ïî ýòîé ïðè÷èíå îïåðàòîð ϕ
íåîäíîçíà÷åí äëÿ íà÷àëüíûõ îòðåçêîâ ñëîâ. Óñòðàíèòü ýòî ìîæíî áûëî
áû, ïðèïèñàâ ñïðàâà ê êàæäîìó âõîäíîìó ñëîâó m
p
= 3 ýêçåìïëÿðà áóê-
âû α è ñëåâà ê êàæäîìó âûõîäíîìó ñëîâó m
q
= 3 ýêçåìïëÿðà áóêâû β,
ò. å. ïðèìåíèâ ñòàíäàðòíóþ ïðîöåäóðó âûðàâíèâàíèÿ äëèí ñëîâ. Âîñ-
ïîëüçóåìñÿ áîëåå ýêîíîìíîé ïðîöåäóðîé.
z z z ! w w w !
z
z
z
w
w
w
z
z
z
w
w
w
z
z
z
w
w
w
z
z
z
w
w
w
z
z
z
w
w
w
z
z
z
w
w
w
z
z
z
w
w
w
z
z
z
w
w
w