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\}}_{\Sigma}, 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: