Kuroda Normalform 79

Eine Typ 1 Grammatik ist in Kuroda Normalform, falls alle Regeln eine der 4 Formen haben:

• $A\rightarrow a$
• $A\rightarrow B$
• $A\rightarrow BC$
• $AB\rightarrow CD$

Hierbei stehen $A,B,C,D$ für Variablen und $a$ für ein Terminalsymbol.

• Für jede Typ 1 Grammatik $G$ mit $\varepsilon\neq L\left(G\right)$ gibt es eine Grammatik $G'$ in Kuroda Normalform mit $L\left(G\right)=L\left(G'\right)$
  • Durch aufbrechen der Regeln, ähnlich Chomsky-Normalisierung