IB102 úkol 9, příklad 2 Odevzdání: 26. 11. 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.
2. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B, C, D, E, F}, {a, b, c}, P, S),
P = { S → CB | cab,
A → ε | EbD | aa,
B → A | Cb | b,
C → ε | BbA,
D → aaaD | aaa | ε,
E → aE | bFa | aDF | bDE,
F → bEaa | Fa}.
Pomocí algoritmů z přednášky převeďte gramatiku G na ekvivalentní vlastní gramatiku a následně na
gramatiku v Chomského normální formě. Do řešení uveďte celý postup převodu, zejména následující
mezivýsledky:
a) ke gramatice G ekvivalentní gramatiku G1 bez ε-pravidel (nezapomeňte uvést množinu Nε obsahující
všechny neterminály, které se dají přepsat na ε),
b) ke gramatice G1 ekvivalentní gramatiku G2 bez ε-pravidel a jednoduchých pravidel (uveďte množiny
NX, t.j. množiny všech neterminálů, na které se může X ∈ N přepsat pomocí jednoduchých
pravidel),
c) ke gramatice G2 ekvivalentní vlastní gramatiku G3,
d) ke gramatice G3 ekvivalentní gramatiku G4 v Chomského normální formě (CNF).
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.