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

UptoLike

ВУЗ: 

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

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

Рубрика: 

17
Ëîãè÷åñêàÿ ôóíêöèÿ ðàññìàòðèâàåìîé ìàøèíû îïèñûâàåòñÿ ôóíê-
öèîíàëüíîé ñõåìîé (ðèñ. 3.4).
Òðåáóåòñÿ îïðåäåëèòü, êàê èçìåíÿåòñÿ èíôîðìàöèÿ íà ëåíòå ïðè çà-
äàííûõ íà÷àëüíûõ óñëîâèÿõ.
Ðàññìîòðèì ïåðâûé ñïîñîá îïèñàíèÿ ðàáîòû ìàøèíû Òüþðèíãà, â
êîòîðîì â êàæäîì ñîñòîÿíèè ìàøèíû óêàçûâàåòñÿ ïîñëåäîâàòåëüíîñòü
ñèìâîëîâ â ÿ÷åéêàõ ëåíòû.
Òàêò 1 t
1
 ÿ÷åéêè ñîñòîÿíèÿ Q è ñäâèãà D çàíîñÿòñÿ çíà÷åíèÿ íà÷àëüíîãî
ñîñòîÿíèÿ q
1
è íà÷àëüíîãî ñäâèãà Å è îáîçðåâàåòñÿ ñîäåðæàíèå íà÷àëü-
íîé 4-é ÿ÷åéêè (ñèìâîë 1) ïðè ñîñòîÿíèè q
1
. Â ñîîòâåòñòâèè ñ ôóíêöè-
îíàëüíîé ñõåìîé ðåçóëüòàòîì äàííîãî øàãà áóäåò q
2
α E , ò. å. âûïîëíÿ-
åòñÿ Òüþðèíãîâà êîìàíäà
q
1
1 → q
2
α E ,
ãäå q
2
óêàçûâàåò, íà êàêóþ îïåðàöèþ ïåðåøëè; α ÷òî çàïèñàëè â îáî-
çðåâàåìóþ ÿ÷åéêó; Å íàïðàâëåíèå ñäâèãà ãîëîâêè.
Ñëåäîâàòåëüíî, ñäâèã ãîëîâêè óñòðîéñòâà îáðàùåíèÿ ê ëåíòå îòñóò-
ñòâóåò, à ñèìâîë 1 çàìåíÿåòñÿ â 4-é ÿ÷åéêå íà α.
Ïîëó÷èì
54321
q
2
:1
α
111
↑
Òàêò 2 t
2
Òàê êàê ñäâèãà íå áûëî, òî âíîâü îáîçðåâàåòñÿ 4-ÿ ÿ÷åéêà, íî óæå â
ñîñòîÿíèè q
2
.
q
q
q
!
q
"
q
#
λ
q
"
λ Rq
!
λ Lq
λ Rq
#
λ Lq
#
λ E
q
α Eq
β Eq
Rq
#
λ Rq
#
E
α
q
"
α Lq
α Rq
!
Lq
"
λ Rq
#
α E
β
q
β Lq
β Rq
!
λ Lq
"
Rq
#
β E
Ðèñ. 3.4

Страницы