IB102 – úkol 7, příklad 1 Odevzdání: 18. 11. 2013
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažme následující bezkontextovou gramatiku:
G = ({S, A, B, C, D, E}, {x, y, z}, P, S)
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).
1