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

UptoLike

ВУЗ: 

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

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

Рубрика: 

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(t1),
åñëè ïðèíÿòü z(0) = z
1
. Ýòî è åñòü èñêîìîå ïðåîáðàçîâàíèå âõîäíûõ ñëîâ
àâòîìàòà â âûõîäíûå. Ïîñêîëüêó äëèíà âõîäíûõ ñëîâ äëÿ ýòîãî ïðåîáðà-
çîâàíèÿ íå îãðàíè÷åíà, ìíîæåñòâî äîïóñòèìûõ âõîäíûõ ñëîâ äëÿ íåãî
áåñêîíå÷íî è äàæå íåñ÷åòíî ïðè âñÿêîì F
≥ 2.
Îïåðàòîð ϕ
A
îäíîçíà÷íî îïðåäåëÿåòñÿ çàäàíèåì ôóíêöèè ïåðåõîäîâ
δ è ôóíêöèè âûõîäîâ λ ðàññìàòðèâàåìîãî àâòîìàòà. Ôóíêöèÿ ïåðåõî-
äîâ îïðåäåëÿåò ñîñòîÿíèå a(t) àâòîìàòà â íåêîòîðûé ìîìåíò t àâòî-
ìàòíîãî âðåìåíè ïî âõîäíîìó ñèãíàëó z(t) â òîò æå ñàìûé ìîìåíò è
ñîñòîÿíèé a(t1) â ïðåäûäóùèé ìîìåíò àâòîìàòíîãî âðåìåíè
a(t) = δ(a(t1), z(t)). (4.1)
Ôóíêöèÿ âûõîäîâ îïðåäåëÿåò çàâèñèìîñòü âûõîäíîãî ñèãíàëà îò òåõ
æå ñàìûõ ïåðåìåííûõ
w(t) = λ(a(t1), 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).

Страницы