IB102 – úkol 7, příklad 2 Odevzdání: 10. 11. 2014
Vypracoval(a): UČO:
Skupina:
2. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B}, {a, b}, P, S),
P = { S → Bb | Aa,
A → Sb | a | Bb | aA,
B → BA | Aa | b}.
Pomocí algoritmu z přednášky zkonstruujte ke gramatice G ekvivalentní nelevorekurzivní
gramatiku bez ε-pravidel. Uveďte, jaké uspořádání neterminálů jste zvolili při odstraňování
nepřímé levé rekurze a rovněž celý postup převodu. Nezapomeňte stručně zdůvodnit,
proč gramatika G splňuje vstupní podmínku uvedeného algoritmu.