FORM LN JAZYKY A AUTOMATY I
CVICEN 8
1. Uva ujme bezkontextovou gramatiku G = (fR; K; I; Dg; fa; e; +; ; (; )g; P; R)s pravidly
P : R ! R + K j K
K ! KI j I
I ! I j D
D ! (R) j a j e
a) Vytvortez sobn kov automatA,kter modelujesyntaktickouanal zujazykaL(G)metodou
shora dolu.
b) Vytvorte z sobn kov automat A, kter modeluje syntaktickou anal zu jazyka L(G)
metodou zdola nahoru.
2. Necht' = fa; bg , L1 = fabaabg fai
bai+1b j i 1g a
L2 = fabg fai
bai+1b j i 1g fag+ fbg.
a) Navrhnete deterministick z sobn kov automat rozpozn vaj c jazyk L2.
b) Navrhnete z sobn kov automat pro jazyk (L1 \L2)
3. Pou it m algoritmu z predn ky zkonstruujte k dan mu z sobn kov mu automatu A (akceptuj
c mu pr zdnou pamet ) ekvivalentn bezkontextovou gramatiku.
A = (fq0; q1g; f0; +g; fZ0; Xg; ; q0; Z0; ;g)
: (q0; 1; Z0) = f(q0; XZ0)g
(q0; "; Z0) = f(q0; ")g
(q0; 1; X) = f(q0; XX)g
(q1; 1; X) = f(q1; ")g
(q0; 0; X) = f(q1; X)g
(q1; 0; Z0) = f(q0; Z0)g
1