• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Konstruktion der Chomsky-Normalform

Contents

  • Die Chomsky-Normalform
  • Konstruktion der CNF
    • Schritt 1
    • Schritt 2
    • Schritt 3
    • Schritt 4
  • Beispiele
    • Die Sprache der Palindrome
  • Weiterführende Links und Quellen
Dieser Artikel könnte inhaltliche Fehler beinhalten. Bitte lest euch die Kommentare durch.

Die Chomsky-Normalform ist eine bestimmte Art, eine kontextfreie Grammatik zu formulieren. Dabei haben nur die Produktionsregeln eine festgelegte Form, alles andere ist wie immer. Die Chomsky-Normalform kommt bei dem CYK-Algorithmus, der das Wortproblem für kontextfreie Grammatiken löst, zum Einsatz. Jede kontextfreie Grammatik kann in Chomsky-Normalform gebracht werden.

Die Chomsky-Normalform

Das Besondere an der Chomsky-Normalform ist, dass alle Regeln der Grammatik $G (V, \Sigma, P, S)$ folgende Form haben: $A \rightarrow BC$ oder $A \rightarrow a$. Dabei sind $A, B, C \in V$ und $a \in \Sigma$.

Falls die Grammatik in der Lage ist, das Leere Wort $\varepsilon$ zu erzeugen, dann fügt man folgende Sonderregel hinzu: $S' \rightarrow S | \varepsilon$. Dabei darf S' niemals auf der rechten Seite einer Produktion stehen.

Eine Eigenschaft der Chomsky-Normalform ist, dass jedes Wort aus $2 \cdot |w| - 1$ Ableitungen gebildet werden kann. (Falls das leere Wort gebildet werden kann sind es $2 \cdot |w|$ Ableitungen für jedes nicht-leere Wort und eine Ableitung für das leere Wort) In jedem Ableitungsschritt erhält man entweder ein Terminal, oder ein weiteres Nicht-Terminal.

Konstruktion der CNF

Aus einer Grammatik $G (V, \Sigma, P, S)$ kann mit folgenden vier Schritten eine Grammatik $G' (V', \Sigma, P', S)$ in Chomsky-Normalform (CNF) erstellt werden:

Schritt 1

Immer wenn ein Symbol aus $\Sigma$ in einer Produktion steht, wird dieses durch $Y_a$ ersetzt und eine neue Produktion $Y_a \rightarrow a$ zu P' hinzugefügt.

Es ist somit sichergestellt, dass alle Regeln entweder nur Nicht-Terminale auf der rechten Seite der Produktion stehen haben oder $\varepsilon$ oder dass dort ein einzelnes Terminal steht.

Schritt 2

Immer wenn mehr als zwei Variablen auf der rechten Seite stehen, werden diese durch neue ersetzt. Sagen wir es stehen rechts m Variablen. Dann führt man m - 2 neue Variablen ein, fügt diese zu V' hinzu, und macht aus einer Regel $A \rightarrow B_1 B_2 ... B_m$ die Regeln $A \rightarrow B_1 C_1, C_1 \rightarrow B_2 C_2, ..., C_{i+1} \rightarrow B_i C_i ... C_{m-2} \rightarrow B_{m-3} C_{m-3}$.

An dieser Stelle ist sichergestellt, dass alle Regeln entweder nur ein oder zwei Nicht-Terminale auf der rechten Seite der Produktion stehen haben oder $\varepsilon$ oder dass dort ein einzelnes Terminal steht.

Schritt 3

Nun wollen wir alle $\varepsilon$-Übergänge entfernen.

Um dies zu erreichen, suchen wir alle Regeln, die nach $\varepsilon$ abbilden, also von der Form $A \rightarrow \varepsilon$ sind. Dabei streichen wir die Regeln $A \rightarrow \varepsilon$. Falls A nun nicht mehr auf der linken Seite auftaucht, streichen wir es überall aus der rechten Seite. Falls dabei eine Regel zu $B \rightarrow \varepsilon$ wird, streichen wir auch diese. Das wiederholen wir so lange, bis keine $\varepsilon$-Übergänge mehr vorhanden sind. Am Ende fügen wir die Regel $S' \rightarrow S | \varepsilon$ hinzu, falls die Grammatik auf das leere Wort abbilden konnte.

Nun ist sichergestellt, dass alle Regeln entweder nur ein oder zwei Nicht-Terminale auf der rechten Seite der Produktion stehen haben oder dass dort ein einzelnes Terminal steht. Allerdings kann es noch Kreise in der Ableitung geben, die man entfernen kann.

Schritt 4

In diesem Schritt entfernen wir eventuell vorhandene Kettenregeln, also Regeln der Form $A_1 \rightarrow A_2 \rightarrow A_3 \rightarrow A_u \rightarrow A_1$. Diese findet man mit einer Tiefensuche. Dann ersetzt man alle $A_2, ..., A_u$ durch $A_1$. Die Regel $A_1 \rightarrow A_1$ kann entfernt werden, da sie ja nichts ändert.

Beispiele

Die Sprache der Palindrome

Gegeben sei folgende Grammatik: $G(\underbrace{{S}}{V}, \underbrace{{a,b}}, S, P)$ mit $P = {S \rightarrow \varepsilon | a | b | aSa | bSb }$.

Schritt 1

$S \rightarrow \varepsilon | Y_a | Y_b | Y_aSY_a | Y_bSY_b$ $Y_a \rightarrow a$ $Y_b \rightarrow b$

Schritt 2

$S \rightarrow \varepsilon | Y_a | Y_b | Y_aC_1 | Y_bC_2$ $C_1 \rightarrow SY_a$ $C_2 \rightarrow SY_b$ $Y_a \rightarrow a$ $Y_b \rightarrow b$

Schritt 3

$S \rightarrow Y_a | Y_b | Y_aC_1 | Y_bC_2$ $C_1 \rightarrow SY_a$ $C_2 \rightarrow SY_b$ $Y_a \rightarrow a$ $Y_b \rightarrow b$ $S' \rightarrow S | \varepsilon$

Schritt 4

Keine Kettenregel vorhanden.

Ergebnis

Nun werden noch einzelne Nicht-Terminale durch die möglichen Terminale ersetzt und man ist fertig.

Damit ist die Grammatik: $G_{CNF} ({S, S', Y_a, Y_b, C_1, C_2}, {a,b}, S', P'))$ mit folgenden Produktionen P': $P' = {S \rightarrow a | b | Y_aC_1 | Y_bC_2,$ $~ C_1 \rightarrow SY_a,$ $~ C_2 \rightarrow SY_b,$ $~ Y_a \rightarrow a,$ $~ Y_b \rightarrow b,$ $~ S' \rightarrow S | \varepsilon}$

Sie ist also nicht schöner oder einfacher geworden, hat aber eine bestimmte Struktur erhalten.

Weiterführende Links und Quellen

  • Wikipedia
  • Uwe Schöning: Theoretische Informatik- kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, S. 44, DNB 986529222.
  • KIT:
    • Skript von Prof. Dr. Dorothea Wagner, S. 98
    • Übung vom 02.02.2012 - Hier ist ein sehr gutes, detailliertes Beispiel!

Published

Feb 11, 2012
by Martin Thoma

Category

German posts

Tags

  • lecture-notes 11
  • Theoretical computer science 9

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor