Generativní síla normálních forem
Tvrzení: Pro každou BKG existuje ekvivalentní gramatika G’ v Chomského normální formě.
Důkaz: Viz. str. 348 v knize [Meduna: Automata and Languages]
Tvrzení: Pro každou BKG existuje ekvivalentní gramatika G’ v Greibachové normální formě.
Pozn.: Základní vlastnosti CNF a GNF:
CNF: pokud S Þn w; w Î T* potom n = 2|w| – 1
GNF: pokud S Þn w; w Î T* potom n = |w|
4/31
Důkaz: Viz. str. 376 v knize [Meduna: Automata and Languages]