Kuroda-Normalform

Die Kuroda-Normalform ist ein Begriff der Theoretischen Informatik, der im Zusammenhang mit kontextsensitiven Sprachen von Interesse ist. Sie ist nach dem Linguisten Sige-Yuki Kuroda benannt und beschreibt eine Normalform der monotonen Grammatiken, also eine Teilmenge der monotonen Grammatiken, die gegenüber der Menge aller monotonen Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen. Weil monotone Grammatiken und kontextsensitive Grammatiken gelegentlich nicht unterschieden werden, wird die Kuroda-Normalform auch als Normalform der kontextsensitiven Grammatiken bezeichnet.

Die Kuroda-Normalform ist eine Verallgemeinerung der Chomsky-Normalform, die eine Normalform für kontextfreie Grammatiken ist.

Definition

Eine formale Grammatik ist in Kuroda-Normalform (kurz KNF, nicht zu verwechseln mit „KNF“ – Konjunktive Normalform), wenn alle Produktionen die folgende Form haben:

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

wobei $A$, $B$, $C$ und $D$ Variablen sind und $a$ ein Terminalsymbol ist.

Falls die zweite und die vierte Regelform nicht vorkommen, liegt die Grammatik in der Chomsky-Normalform vor.

Eigenschaften

• Jede Grammatik in Kuroda-Normalform ist eine monotone Grammatik.
• Zu jeder monotonen Grammatik $G_{1}$ mit $\varepsilon \notin L(G_{1})$ existiert eine monotone Grammatik $G_{2}$ in Kuroda-Normalform, die die gleiche Sprache erzeugt, das heißt, $L(G_{1})=L(G_{2})$. $G_{2}$ wird dann auch eine Kuroda-Normalform der monotonen Grammatik $G_{1}$ genannt.

Umwandlung einer Grammatik in Kuroda-Normalform

Sei $G_{1}=(V_{1},\Sigma ,P_{1},S)$ eine monotone Grammatik mit $\epsilon \notin L(G_{1})$. Eine Kuroda-Normalform $G_{2}=(V_{2},\Sigma ,P_{2},S)$ von $G_{1}$ kann so konstruiert werden:

• Alle in $P_{1}$ auftretenden Terminalsymbole $a$, welche nicht alleine auftreten, werden jeweils durch eine neue Variable $A_{a}$ ersetzt, und für jedes Terminalsymbol $a$ wird die neue Produktionen $A_{a}\rightarrow a$ eingeführt.
• Jede Produktion der Form $A\rightarrow A_{1}A_{2}\dotso A_{k}$ ersetzt man durch folgende neuen Produktionen: $A\rightarrow A_{1}B_{1}$, $B_{i}\rightarrow A_{i+1}B_{i+1}$ für alle $i\in \{1,\dotsc ,k-3\}$ und $B_{k-2}\rightarrow A_{k-1}A_{k}$. Dabei seien $B_{1},\dotsc ,B_{k-2}$ neue Variablen.
• Jede Produktion der Form $A_{1}A_{2}\dotso A_{l}\rightarrow B_{1}B_{2}\dotso B_{k}$, $2\leq l\leq k$ mit $3\leq k$ ersetzt man durch folgende neuen Produktionen: $A_{1}A_{2}\rightarrow B_{1}C_{1}$, für alle $i\in \{1,\dotsc ,l-2\}$: $C_{i}A_{i+2}\rightarrow B_{i+1}C_{i+1}$, für alle $i\in \{l-1,\dotsc ,k-3\}$: $C_{i}\rightarrow B_{i+1}C_{i+1}$ und $C_{k-2}\rightarrow B_{k-1}B_{k}$. Dabei seien $C_{1},\dotsc ,C_{k-2}$ neue Variablen.

Die so erzeugte Grammatik ist in Kuroda-Normalform und produziert dieselbe Sprache wie die Grammatik zuvor.

Révész-Normalform

Jede monotone Grammatik $G_{1}=(V_{1},\Sigma ,P_{1},S)$ in Kuroda-Normalform kann in eine kontextsensitive Grammatik $G_{2}=(V_{2},\Sigma ,P_{2},S)$ in Révész-Normalform überführt werden. Dazu werden für jede Produktionsregel der Form $AB\rightarrow CD\in P_{1}$ zwei neue Nichtterminale $W,Z\in V_{2}$ eingeführt und die Regel durch vier Regeln ersetzt:

• $AB\rightarrow AZ$
• $AZ\rightarrow WZ$
• $WZ\rightarrow WD$
• $WD\rightarrow CD$

Eine kontextsensitive Grammatik ist in Révész-Normalform, wenn alle Produktionen die folgende Form haben:

• $AB\rightarrow AC$
• $AB\rightarrow CB$
• $A\rightarrow BC$
• $A\rightarrow B$
• $A\rightarrow a$

Dabei sind $A$, $B$ und $C$ Variablen und $a$ ist ein Terminalsymbol.

Zu jeder kontextsensitiven Grammatik $G_{1}$ mit $\varepsilon \notin L(G_{1})$ existiert eine kontextsensitive Grammatik $G_{2}$ in Révész-Normalform, die die gleiche Sprache erzeugt, das heißt, $L(G_{1})=L(G_{2})$.

Literatur

• Benedek Nagy: Derivation Trees for Context-Sensitive Grammars. In: Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008. World Scientific Pub Co, 2008, ISBN 981-4317-60-8, S. 182 (eingeschränkte Vorschau in der Google-Buchsuche).