IB102 úkol 7, příklad 1 Odevzdání: 14. 11. 2016
Jméno: UČO: Skupina:
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 = ({S, B, C, D, E}, {a, b, c}, P, S),
P = { S → cSCb | aB | D,
B → CB | aEB,
C → Bab | Sa,
D → aS | a | ε
E → b | ε, }.
Pomocí algoritmů z přednášky převeďte gramatiku G na ekvivalentní 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),
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.