FORM LN JAZYKY A AUTOMATY I
CVICEN 9
1. Necht' L je libovoln jazyk nad abecedou a ] symbol nepatr c do abecedy . De nujme
jazyk Q nad abecedou f]gtakto:
Q = fu]v j juj = jvj; u; v 2 Lg
a) Doka te, e kdy L je regul rn jazyk, tak Q je bezkontextov jazyk.
b) Rozhodnete, jestli pro libovoln bezkontextov jazyk L, je jazyk Q taky bezkontextov .
2. Je d n Turinguv stroj M = (fg; h; h0; k; l; fg; fa; bg; fa; b; M; N; N0; Bg; ; h0; ffg), kde
: (h0; a) = f(g; N0; R)g
(h; a) = f(g; N; O); (h; a; R); (h; a; L)g
(g; b) = f(h; M; O); (g; b; R); (g; b; L)g
(h; x) = f(h; x; R); (h; x; L)g x 2 fb; N; Mg
(g; y) = f(g; y; R); (g; y; L)g y 2 fa; N; Mg
(h; N0) = f(k; N0; R)g
(k; N) = f(k; N; R)g
(k; M) = f(l; M; R)g
(l; M) = f(l; M; R)g
(l; B) = f(f; N0; O)g
Stroj M akceptuje jazyk L(M) fa; bg . Popi te jazyk L(M).
3. Necht' L je jazyk akceptovan z sobn kov m automatem A. Navrhnete z sobn kov automat
akceptuj c jazyk L1997.
1