141.20.29.24: /* Révész-Normalform */

2023-10-26T11:26:26Z

Révész-Normalform

Neue Seite

Die '''Kuroda-Normalform''' ist ein Begriff der [[Theoretische Informatik|Theoretischen Informatik]], der im Zusammenhang mit [[Kontextsensitive Sprache|kontextsensitiven Sprachen]] von Interesse ist. Sie ist nach dem [[Linguist]]en [[Sige-Yuki Kuroda]] benannt und beschreibt eine Normalform der [[Monotone Grammatik|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 [[Produktionsregel|Produktionen]]. Weil monotone Grammatiken und [[kontextsensitive Grammatik]]en 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:
* <math>A \rightarrow a</math>
* <math>A \rightarrow B</math>
* <math>A \rightarrow BC</math>
* <math>AB \rightarrow CD</math>
wobei <math>A</math>, <math>B</math>, <math>C</math> und <math>D</math> Variablen sind und <math>a</math> 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 <math>G_1</math> mit <math>\varepsilon\notin L(G_1)</math> existiert eine monotone Grammatik <math>G_2</math> in Kuroda-Normalform, die die gleiche Sprache erzeugt, das heißt, <math>L(G_1)=L(G_2)</math>. <math>G_2</math> wird dann auch eine Kuroda-Normalform der monotonen Grammatik <math>G_1</math> genannt.

== Umwandlung einer Grammatik in Kuroda-Normalform ==
Sei <math>G_1=(V_1,\Sigma,P_1,S)</math> eine monotone Grammatik mit <math>\epsilon\notin L(G_1)</math>. Eine Kuroda-Normalform <math>G_2=(V_2,\Sigma,P_2,S)</math> von <math>G_1</math> kann so konstruiert werden:

* Alle in <math>P_1</math> auftretenden Terminalsymbole <math>a</math>, welche nicht alleine auftreten, werden jeweils durch eine neue Variable <math>A_a</math> ersetzt, und für jedes Terminalsymbol <math>a</math> wird die neue Produktionen <math>A_a\rightarrow a</math> eingeführt.
* Jede Produktion der Form <math>A\rightarrow A_1A_2\dotso A_k</math> ersetzt man durch folgende neuen Produktionen: <math>A\rightarrow A_1B_1</math>, <math>B_i\rightarrow A_{i+1}B_{i+1}</math> für alle <math>i\in\{1,\dotsc,k-3\}</math> und <math>B_{k-2}\rightarrow A_{k-1}A_k</math>. Dabei seien <math>B_1,\dotsc,B_{k-2}</math> neue Variablen.
* Jede Produktion der Form <math>A_1A_2\dotso A_l\rightarrow B_1B_2\dotso B_k</math>, <math>2\leq l\leq k</math> mit <math>3\leq k</math> ersetzt man durch folgende neuen Produktionen: <math>A_1A_2\rightarrow B_1C_1</math>, für alle <math>i\in\{1,\dotsc,l-2\}</math>: <math>C_i A_{i+2}\rightarrow B_{i+1}C_{i+1}</math>, für alle <math>i\in\{l-1,\dotsc,k-3\}</math>: <math>C_i\rightarrow B_{i+1}C_{i+1}</math> und <math>C_{k-2}\rightarrow B_{k-1}B_k</math>. Dabei seien <math>C_1,\dotsc,C_{k-2}</math> 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 <math>G_1=(V_1,\Sigma,P_1,S)</math> in Kuroda-Normalform kann in eine kontextsensitive Grammatik <math>G_2=(V_2,\Sigma,P_2,S)</math> in Révész-Normalform überführt werden.
Dazu werden für jede Produktionsregel der Form <math>AB \rightarrow CD \in P_1</math> zwei neue Nichtterminale <math>W,Z\in V_2</math> eingeführt und die Regel durch vier Regeln ersetzt:
*<math>AB \rightarrow AZ</math>
*<math>AZ \rightarrow WZ</math>
*<math>WZ \rightarrow WD</math>
*<math>WD \rightarrow CD</math>

Eine kontextsensitive Grammatik ist in Révész-Normalform, wenn alle Produktionen die folgende Form haben:
*<math>AB \rightarrow AC</math>
*<math>AB \rightarrow CB</math>
*<math>A \rightarrow BC</math>
*<math>A \rightarrow B</math>
*<math>A \rightarrow a</math>
Dabei sind <math>A</math>, <math>B</math> und <math>C</math> Variablen und <math>a</math> ist ein Terminalsymbol.

Zu jeder kontextsensitiven Grammatik <math>G_1</math> mit <math>\varepsilon\notin L(G_1)</math> existiert eine kontextsensitive Grammatik <math>G_2</math> in Révész-Normalform, die die gleiche Sprache erzeugt, das heißt, <math>L(G_1)=L(G_2)</math>.

== Literatur ==
*{{Literatur|Autor=Benedek Nagy|Titel=Derivation Trees for Context-Sensitive Grammars|Seiten=182|Verlag=World Scientific Pub Co|Sammelwerk=Automata, Formal Languages and Algebraic Systems: Proceedings of AFLAS 2008|Jahr=2008|ISBN=981-4317-60-8|Online={{Google Buch|BuchID=xuaR2bJq0rcC|Seite=182}}}}

[[Kategorie:Theorie formaler Sprachen]]
[[Kategorie:Normalform]]

Kuroda-Normalform - Versionsgeschichte

141.20.29.24: /* Révész-Normalform */