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: