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

UptoLike

ВУЗ: 

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

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

Рубрика: 

23
íîãî ðÿäà. Äëÿ ðåàëèçàöèè ñëîæåíèÿ íåîáõîäèìî èñïîëüçîâàòü ôóíêöè-
îíàëüíóþ ñõåìó ìàøèíû Òüþðèíãà, èçîáðàæåííóþ íà ðèñ. 3.6.
Èëè èñïîëüçîâàòü ñëåäóþùóþ ñèñòåìó êîìàíä (âûïèñàíû òîëüêî òå,
êîòîðûå ïîíàäîáÿòñÿ ïðè ñîçäàíèè ïîñëåäîâàòåëüíîñòè êîíôèãóðàöèé):
q
0
1 → q
2
λ R (1)
q
2
1 → q
2
1 R (2)
q
2
* → q
2
* R (3)
q
2
λ → q
1
1Å (4)
q
1
1 → q
1
1 L (5)
q
1
λ → q
0
λ R (6)
q
0
* → ! λ Å (7)
q
1
* → q
1
* L (8)
Òàêò 1 t
1
q
0
1 → q
2
λ R, ò. å. âìåñòî ïåðâîé 1 óñòàíàâëèâàåòñÿ ïðîáåë è â
ñîñòîÿíèè q
2
îáîçðåâàåòñÿ âòîðàÿ 1, òàê êàê ñäâèã äîëæåí áûòü âïðàâî.
Òàêò 2 t
2
q
2
1 → R (çàïèñàíî â óïðîùåííîé ôîðìå), ñëåäîâàòåëüíî ñèìâîë íå
ìåíÿåòñÿ è ñîñòîÿíèå òîæå, ïîýòîìó ïåðåõîäÿ íàïðàâî îò 1 ê 1, áó-
äåì âñå âðåìÿ îñòàâëÿòü èõ â ÿ÷åéêàõ, îñòàâàÿñü â ñîñòîÿíèè q
2
. Ïîïàâ
íà çíàê *, åãî òîæå îñòàâèì, òàê êàê q
2
*→ R.
Ýòîò ñäâèã âïðàâî áóäåò ïðîäîëæàòüñÿ â òå÷åíèå 9 òàêòîâ äî òåõ
ïîð, ïîêà â òàêòå 11 íå ïîïàäåì â ïóñòóþ ÿ÷åéêó.
Òàêòû 110 (t
1
t
10
)
⇒ 4
G
2
:
λ
11111* 1111
↑↑↑
...
↑...↑
J
1
J
2
J
3
J
6
J
01
q
q
q
1
q
λ RL R
λ
Rq
Rq
∗
λ LR
Ðèñ. 3.6

Страницы