Kuroda-Normalform

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

Umwandlung einer Grammatik in Kuroda-Normalform

Sei G1 = (V1,Σ,P1,S) eine kontextsensitive Grammatik mit \epsilon\notin L(G_1). Eine Kuroda-Normalform G2 = (V2,Σ,P2,S) von G1 kann so konstruiert werden:

  • Alle in P1 auftretenden Terminalsymbole a werden jeweils durch eine neue Variable Aa 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.


Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kuroda — bezeichnet: einen japanischen Klan: Kuroda (Klan) Kuroda Nagamasa (Daimyō) Kuroda Yoshitaka (Daimyō) den Alternativnamen eines danach benannten Lehens: Fukuoka (Han) Kuroda ist der Familiennamen folgender Personen: Aki Kuroda (* 1944),… …   Deutsch Wikipedia

  • Chomsky Normalform — Die Chomsky Normalform (Abk.: CNF) ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach… …   Deutsch Wikipedia

  • Chomsky-Normalform — Die Chomsky Normalform (Abk.: CNF) ist in der theoretischen Informatik eine Normalform für kontextfreie Grammatiken. Sie ist nach dem Linguisten Noam Chomsky benannt und kommt beim CYK Algorithmus zum Einsatz. Eine kontextfreie Grammatik in… …   Deutsch Wikipedia

  • CNF — Die Chomsky Normalform (Abk.: CNF) ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach… …   Deutsch Wikipedia

  • Chomskynormalform — Die Chomsky Normalform (Abk.: CNF) ist eine kontextfreie Grammatik mit einer besonders einfachen Struktur der Produktionen. Sie ist ein Begriff aus der Theorie der formalen Sprachen, einem Teilbereich der Theoretischen Informatik. Sie ist nach… …   Deutsch Wikipedia

  • Kontextsensitive Grammatik — Die kontextsensitiven Grammatiken (kurz CSG, von engl. context sensitive grammar) sind eine Klasse formaler Grammatiken und identisch mit den Typ 1 Grammatiken der Chomsky Hierarchie. Sie zeichnen sich dadurch aus, dass einzelne… …   Deutsch Wikipedia

  • KNF — Die Abkürzung KNF steht: im Bereich der Aussagenlogik für die Konjunktive Normalform bei den formale Sprachen für die Kuroda Normalform für den Verein Kanu und Naturfreunde Frankfurt Kuki National Front eine Befreiungsorganisation in Indien für… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”