Chomsky-Normalform

Sei $G$ eine kontextfreie Grammatik (vgl. Chomsky-Hierarchie), also $G\in Typ_{2}$. Sei das leere Element $\epsilon \notin L\left(G\right)$.

$G$, mit $G=\left(N,\Sigma ,P,S\right)$, ist in Chomsky-Normalform, wenn alle Regeln (= Produktionen) aus $P$ die Form $A\rightarrow BC$ oder $A\rightarrow b$ haben, wobei $A,B,C\in N$ (Nichtterminale) und $b\in \Sigma$ (Terminale).

Für alle $G'\in Typ_{2}$ mit $\epsilon \notin L\left(G'\right)$ gibt es ein $G\in Typ_{2}$, mit $L\left(G\right)=L\left(G'\right)$, in Chomsky-Normalform.

Siehe auch

• Greibach-Normalform