Informatik

Was ist die Chomsky-Normalform?

Eine kontextfreie Grammatik ist in Chomsky-Normalform, wenn alle Produktionen die Formen

A→BCoderA→aA\to BC \quad\text{oder}\quad A\to a

haben, ggf. zusätzlich S→εS\to\varepsilon.