Generative Power of
Normal Forms
Theorem: For every CFG G, there is an equivalent grammar G’ in
Chomsky
normal form.
Proof: See page 348 in [Meduna:
Automata and Languages]
Theorem: For every CFG G, there is an equivalent grammar G’ in
Greibach
normal form.
Proof: See page 376 in [Meduna:
Automata and Languages]
Note: Main
properties of CNF and
GNF:
CNF: if S Þn w; w Î T* then n = 2|w| – 1
GNF: if S Þn w; w Î T* then n = |w|
4/31