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.

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

• A → a {\displaystyle A\rightarrow a}
• A → B {\displaystyle A\rightarrow B}
• A → B C {\displaystyle A\rightarrow BC}
• A B → C D {\displaystyle AB\rightarrow CD}

wobei A {\displaystyle A} , B {\displaystyle B} , C {\displaystyle C} und D {\displaystyle D} Variablen sind und a {\displaystyle a} ein Terminalsymbol ist.

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

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

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

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

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

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

• A B → A Z {\displaystyle AB\rightarrow AZ}
• A Z → W Z {\displaystyle AZ\rightarrow WZ}
• W Z → W D {\displaystyle WZ\rightarrow WD}
• W D → C D {\displaystyle WD\rightarrow CD}

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

• A B → A C {\displaystyle AB\rightarrow AC}
• A B → C B {\displaystyle AB\rightarrow CB}
• A → B C {\displaystyle A\rightarrow BC}
• A → B {\displaystyle A\rightarrow B}
• A → a {\displaystyle A\rightarrow a}

Dabei sind A {\displaystyle A} , B {\displaystyle B} und C {\displaystyle C} Variablen und a {\displaystyle a} ist ein Terminalsymbol.

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

• 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).