IB102 – úkol 7, příklad 1 Odevzdání: 10. 11. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Uvažte následující gramatiku G:
G = ({S, A, B, C}, {a, b}, P, S),
P = { S → A | SabB | C,
A → ε | AaS,
B → b | AA,
C → aS}.
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).