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 kontextsensitiven Grammatiken, also eine Teilmenge der kontextsensitiven Grammatiken, die gegenüber der Menge der allgemeinen kontextsensitiven Grammatiken nichts an Ausdrucksstärke einbüßt. Die Bedeutung der Kuroda-Normalform liegt in der sehr einfachen Struktur der Produktionen.

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

Definition

Eine formale Grammatik ist in Kuroda-Normalform (kurz KNF), 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.

Im Fall, dass 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 kontextsensitiven Grammatik G₁ mit $\epsilon\notin L(G_1)$ existiert eine Grammatik G₂ in Kuroda-Normalform, die die gleiche Sprache erzeugt, das heißt, L(G₁) = L(G₂). G₂ wird dann auch eine Kuroda-Normalform der kontextsensitiven Grammatik G₁ genannt.

Umwandlung einer Grammatik in Kuroda-Normalform

Sei G₁ = (V₁,Σ,P₁,S) eine kontextsensitive Grammatik mit $\epsilon\notin L(G_1)$. Eine Kuroda-Normalform G₂ = (V₂,Σ,P₂,S) von G₁ kann so konstruiert werden:

• Alle in P₁ auftretenden Terminalsymbole a 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_1A_2\cdots A_k$ ersetzt man durch folgende neuen Produktionen: $A\rightarrow A_1B_1$, $B_i\rightarrow A_{i+1}B_{i+1}$ für alle $i\in\{1,\cdots,k-3\}$ und $B_{k-2}\rightarrow A_{k-1}A_k$. Dabei seien $B_1,\cdots,B_{k-2}$ neue Variablen.
• Jede Produktion der Form $A_1A_2\cdots A_l\rightarrow B_1B_2\cdots B_k$, $2\leq l\leq k$ mit $3\leq k$ ersetzt man durch folgende neuen Produktionen: $A_1A_2\rightarrow B_1C_1$, für alle $i\in\{1,\cdots,l-2\}$: $C_i A_{i+2}\rightarrow B_{i+1}C_{i+1}$, für alle $i\in\{l-1,\cdots,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,\cdots,C_{k-2}$ neue Variablen.

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