IB102 – úkol 6, příklad 3 Odevzdání: 16. 11. 2015
Vypracoval(a): UČO:
Skupina:
3. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B, C, D}, {a, b}, P, S),
P = { S → BaC | SbbA | ε,
A → a | BA | ε,
B → A | bbCS | a,
C → bDC | aC,
D → C | a}.
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í mezi-
vý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ře-
psat),
c) ke gramatice G2 ekvivalentní vlastní gramatiku G3,
d) ke gramatice G3 ekvivalentní gramatiku G4 v Chomského normální formě (CNF).