FORM LN JAZYKY A AUTOMATY I
CVICEN 7
1. Preved'te do Greibachov norm ln ho tvaru gramatiku
G = (fS; L; T; Fg; fand; or; number; +; ; ; =; (; )g; P; S),kde
P : S ! S and L j S orL j L
L ! L + T j L T j T
T ! T F j T=F j F
F ! number j (S)
(and je termin lem gramatiky G; analogicky jsou termin ln mi symboly i or; number).
2. Je d na gramatika G = (fA; B; Cg; fa; b; cg; P; A) s pravidly:
P : A ! BBC A ! CaaB A ! c
B ! AabB B ! Ba B ! ab
C ! cc C ! BA C ! "
Pou it m algoritmu z predn ky navrhnete z sobn kov automat akceptuj c jazyk L(G).
3. Jedan z sobn kov automatA = (fqg; fa1; a2; a3; b1; b2g; fZ0; Sg; ; q; Z0; ;) akceptuj c pr zdnou
pamet , kde
(q; a1; Z0) = (q; SSSZ0)
(q; a2; Z0) = (q; SZ0)
(q; a3; Z0) = (q; SSSSSZ0)
(q; a1; S) = (q; SSSS)
(q; a2; S) = (q; SS)
(q; a3; S) = (q; SSSSSS)
(q; b1; S) = (q; b2; S) = (q; b1; Z0) = (q; b2; Z0) = (q; ")
Popi te jazyk akceptovan automatem A. Sv tvrzen oduvodnete.
4. Bud' H gramatika v Greibachov norm ln m tvaru a r slovo, r 2 L(H), kter ho d lka je jrj = l.
Jak je d lka odvozen slova r v H?
1