Domácí úkol č. 4
Příklad 1 (12 bodů)
Uvažme následující bezkontextovou gramatiku: G = ({S, A, B, C, D, E}, {x, y, z}, P, S)
CFG s pravidly
P = {S → Bx | ε
A → Sx | DS
B → Ay | AB | Ez
C → xxz
D → y | ExC | ExS | ε
E → Ex | EA}
Převeďte gramatiku G na ekvivalentní vlastní gramatiku neobsahující levou rekurzi.
Do řešení uveďte celý postup převodu, zejména následující mezivýsledky:
• gramatiku G1 (ekvivalentní G), která neobsahuje nepoužitelné symboly;
• gramatiku G2 (ekvivalentní G1), která neobsahuje nepoužitelné symboly
ani ε-pravidla (nezapomeňte uvést množinu Nε obsahující všechny neterminály,
které se dají přepsat na ε);
• gramatiku G3 (ekvivalentní G2), která neobsahuje nepoužitelné symboly,
ε-pravidla ani jednoduchá pravidla;
• výslednou gramatiku G4 (ekvivalentní G3), která neobsahuje nepoužitelné
symboly, ε-pravidla, jednoduchá pravidla, nepřímou ani přímou levou rekurzi
(uveďte, jaké uspořádání neterminálů jste zvolili při odstraňování
nepřímé levé rekurze).
Příklad 2 (8 bodů)
Dokažte pomocí Pumping lemmatu, že jazyk
L = {am
.bn
.cmn
| m, n ∈ N}
není bezkontextový.
1