Chomsky-Normalform

Definition

Eine Kontextfreie Grammatik $(N,\Sigma ,P,S)$ ist in Chomsky-Normalform, wenn alle Ableitungsregeln die folgende Form haben:

• $A⟶a$ oder $A⟶BC$ mit $A,B,C\in N,a\in \Sigma$
• $S⟶ϵ$ ist erlaubt, wenn es keine Regeln $A⟶BC$ mit $S\in \{B,C\}$ gibt.

Separierte Grammatik
ε freie Grammatik
Kettenregelfreie Grammatik