FORM LN JAZYKY A AUTOMATY I
CVICEN 6
1. Najdete gramatiku v Chomsk ho norm ln m tvaru generuj c jazyk
L = fan
bn
j n 1g+.
2. Bud' G gramatika v Chomsk ho norm ln m tvaru a w slovo, w 2 L(G). Necht' existuje odvozen
slova w v gramatice G d lky n. Jak je d lka slova w?
3. Navrhnete algoritmus, kter k libovoln gramatice G = (N; T; P; S) zkonstruuje ekvivalentn
gramatiku G = (N; T; P; S) takovou, e ka d pravidlo z P obsahuj c na prav strane termin
ln symbol je tvaru A ! a ( A 2 N; a 2 T). Jak ho typu bude gramatika G, zkonstruov
na V mi navr en m algoritmem?
4. Necht' = fa; bg, L1 = fabaabg fai
bai+1b j i 1g a L2 = fabg fai
bai+1b j i 1g fag+ fbg.
a) Popi te jazyk L1 \L2.
b) Doka te, e jazyk L1 \L2 nen bezkontextov .
1