IB102 úkol 10, příklad 1 Odevzdání: 3. 12. 2018
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
1. [2 body] Uvažte následující gramatiku G:
G = ({A, B, C}, {a, b, c}, P, A)
P = {A → Ba | AbC,
B → Bab | ba | AcC,
C → ab | CB | c}
Pomocí algoritmu z přednášky zkonstruujte ke gramatice G ekvivalentní nelevorekurzivní gramatiku.
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.
Následně gramatiku převeďte do Greibachové normální formy. Použijte algoritmus z přednášky
(nebo dokažte, že je vaše gramatika v GNF ekvivalentní G).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.