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

UptoLike

ВУЗ: 

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

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

Рубрика: 

21
âíóòðåííåãî ñîñòîÿíèÿ;
ñîñòîÿíèÿ ëåíòû (ò. å. ñëîâà, çàïèñàííîãî íà ëåíòå);
ïîëîæåíèÿ ãîëîâêè íà ëåíòå.
Êîíôèãóðàöèÿ îáîçíà÷àåòñÿ òðîéêîé ñèìâîëîâ K = α
1
q
i
α
2
, ãäå q
i

òåêóùåå âíóòðåííåå ñîñòîÿíèå, α
1
 ñëîâî ñëåâà îò ãîëîâêè; α
2
 ñëîâî,
îáðàçîâàííîå ñèìâîëîì, îáîçðåâàåìûì ãîëîâêîé, è ñèìâîëîì ñïðàâà
îò íåãî, ïðè÷åì, ñëåâà îò α
1
è ñïðàâà îò α
2
íåò íåïóñòûõ ñèìâîëîâ (ò. å.
ëèáî çàïèñàíî λ, ëèáî íè÷åãî).
Íàïðèìåð, åñëè âíóòðåííåå ñîñòîÿíèå q
i
= abcde, à ãîëîâêà îáîçðå-
âàåò ñèìâîë d, òîãäà êîíôèãóðàöèÿ ìàøèíû Òüþðèíãà K = abcq
i
de, ò. å.
G
E
= =>?@A
↑
Ñòàíäàðòíàÿ íà÷àëüíàÿ êîíôèãóðàöèÿ îáîçíà÷àåòñÿ êàê K
1
=q
1
α, ãäå
q
1
 íà÷àëüíîå ñîñòîÿíèå, à ãîëîâêà îáîçðåâàåò êðàéíèé ëåâûé ñèìâîë.
Ñòàíäàðòíàÿ êîíå÷íàÿ êîíôèãóðàöèÿ èìååò âèä Kz=q
z
α, ãäå q
z
êîíå÷-
íîå ñîñòîÿíèå è âîêðóã îáîçðåâàåìîé ÿ÷åéêè ïóñòûå ñèìâîëû.
Ðàáîòà ìàøèíû Òüþðèíãà ìîæåò áûòü îïèñàíà ñ ïîìîùüþ ïîñëå-
äîâàòåëüíîñòè êîíôèãóðàöèé.
Îïðåäåëåíèå. Åñëè ê íåêîòîðîé êîíôèãóðàöèè ìàøèíû Òüþðèíãà
K ïðèìåíèìà ðîâíî îäíà êîìàíäà, ïðèâîäÿùàÿ ê êîíôèãóðàöèè K,
òî ãîâîðÿò, ÷òî ìåæäó êîíôèãóðàöèÿìè K è Kñóùåñòâóåò îòíîøå-
íèå K
→
T
K, ÷òî îçíà÷àåò: K ïåðåõîäèò â Kïî Òüþðèíãó.
Åñëè æå äëÿ K
1
è K
n
ñóùåñòâóåò ïîñëåäîâàòåëüíîñòü ðàçëè÷íûõ êîí-
ôèãóðàöèé òàêàÿ, ÷òî K
1
→
T
K
2
→
T
K
3
→
T
...
→
T
K
n
, òî òàêàÿ ïîñëåäîâà-
òåëüíîñòü îáîçíà÷àåòñÿ K
1
T
⇒
K
n
. Ïîñëåäîâàòåëüíîñòü êîíôèãóðàöèé
K
1
→
T
K
2
→
T
...
→
T
K
n
îäíîçíà÷íî îïðåäåëÿåòñÿ èñõîäíîé êîíôèãóðàöèåé
K
1
è ïîëíîñòüþ îïèñûâàåò ðàáîòó ìàøèíû Òüþðèíãà, íà÷èíàÿ ñ K
1
.
 êà÷åñòâå ïðèìåðà ðàññìîòðèì ñèñòåìó êîìàíä Σ
Ò
, ñîñòàâëåííóþ
íà îñíîâå ôóíêöèîíàëüíîé ñõåìû, ïðèâåäåííîé íà ðèñ. 3.4 (âûïèñûâàåì
òîëüêî òå êîìàíäû, êîòîðûå ïîíàäîáÿòñÿ äëÿ èëëþñòðàöèè):
q
1
1 → q
2
α E (1) q
1
b → q
1
β L (4) q
4
1 → q
5
λ R (6)
α
2
α
1

Страницы