FORM LN JAZYKY A AUTOMATY I
Re en cvicen 10.
1. G = fS;C;A;B;a;b;M;N;N0;h0;g;h;k;l;f; g; fa;bg; P; S ]
S ! Ah0
A ! aAa jbAb jB
B ! B j
ah0 ! gN0
ah ! Ng jha
ah ! a h 2fa;b;M;N;N0g
bg ! Mh jgb
bg ! b g
h ! h 2fb;N;Mg
h ! h
g ! g 2fa;N;Mg
g ! g
N0h ! kN0
Nk ! kN
Mk ! lM
Ml ! lM
l ! N0f
f ! C
C ! C 2 f g
C ! C
C !
2. ANO. Zkonstruujeme nedeterministick Turinguv stroj Ls jednosmerne nekonecnou p skou,
akceptuj c jazyk L. V pocet stroje Lbude prob hat ve trech etap ch: v prvn se hlava
posune na prav konec vstupn ho retezu a vpravo od neho (nedeterministicky) zap e
slovo y, pricem se soucasne kontroluje, zda toto slovo je akceptov no konecn m automatem
R. Ve druh etape se hlava presune na lev konec retezu a prejde do poc tecn ho
stavu Turingova stroja M. V z verecn etape se simuluje v pocet stroje Mna slove, kter
je pr ve zapsan na p sce.
Predpokl dejme, estroj M(R)m mno inu stavuKM (KR),poc tecn stavqM (qR),prechodovou
relaci M ( R) a mno inu akceptuj c ch stavu FM (FR). D le bud'te r0;r1 nov stavy.
Nakonec, bez str ty obecnosti, mu eme predpokl dat, e stroj Mm na zac tku v poctu
vstupn slovo zapsan na sv p sce tak, e je zleva ohraniceno symbolem 6 c a zprava symbolem
$.
L= (KM KR fr0;r1g; M; M; ;r0;FM)
: (r0;a) = f(r0;a;R)g pro v echna a 2 M
(r0;B) = f(s;b;R) jb 2 R;s 2 R(qR;b)g
(t;B) = f(s;b;R) jb 2 R;s 2 R(t;b)g pro v echna t 2KR
(t;B) = f(r1;$;L)g pro v echna t 2FR
(r1;a) = f(r1;a;L)g pro v echna a 2 M
(r1;6c) = f(qM;6c;R)g
(u;a) = M(u;a) pro v echna u 2KM;a 2 M
1