Ψ Die Informatikseite

Menü
Informatik » Bachelor » Theoretische Informatik » Kontextfreie Sprachen (CFG) » Chomsky Normalform (CNF)
Nutzlose Variablen Kontextfreie Sprachen (CFG) CYK-Algorithmus für das Wortproblem
Unterabschnitte

Chomsky Normalform (CNF)

Definition

In der CNF gibt es nur Regeln der Form

\begin{displaymath}A\rightarrow a\end{displaymath}


\begin{displaymath}A\rightarrow BC\end{displaymath}

Algorithmus zur Eliminierung der Kettenregeln

  1. Finde alle Regel-Ketten der Form

    \begin{displaymath}A_{1}\rightarrow A_{2},\,A_{2}\rightarrow A_{3},\,\ldots\,, A_{n}\rightarrow A_{1}\end{displaymath}

    und entferne sie und ersetze sie durch $A_{1}\rightarrow A_{1}$.

    Numeriere die Nicht-Terminale, so daß $\forall A_{i}\rightarrow A_{j}$ $i<j$ gilt55.

  2. Reduzierung von Regeln

    \begin{displaymath}A_{i}\rightarrow A_{j}\end{displaymath}

    indem das Nonterminal $A_{j}$ gestrichen wird und die Regel

    \begin{displaymath}A_{j}\rightarrow x\end{displaymath}

    in $A_{i}$ integriert werden.

Algorithmus zur Erzeugung der Chomsky-Normalform

  1. Algorithmus zur Eliminierung der Kettenregeln ausführen
  2. Wir fügen für alle $a\in\Sigma$ eine Regel $A_{a}\rightarrow a$ ein und ersetzen alle Terminale in der ursprünglichen Grammatik durch $A_{a}$.

    Also wird zum Beispiel eine Regel $A\rightarrow aBc$ zu

    \begin{displaymath}A\rightarrow A_{a}BA_{c}\,\,\,\,\, A_{a}\rightarrow a\,\,\,\,\,\, A_{c}\rightarrow c\end{displaymath}

  3. Wir zerteilen die Regeln mit mehr als 2 Nonterminalen auf der rechten Seite, in dem wir neue Non-Terminals einfügen. Aus

    \begin{displaymath}A\rightarrow B_{1}B_{2}B_{3}B_{4}B_{5}\end{displaymath}

    wird also

    \begin{displaymath}A\rightarrow B_{1}C_{1}\end{displaymath}


    \begin{displaymath}C_{1}\rightarrow B_{2}C_{2}\end{displaymath}


    \begin{displaymath}C_{2}\rightarrow B_{3}C_{3}\end{displaymath}


    \begin{displaymath}C_{3}\rightarrow B_{4}B_{5}\end{displaymath}

Beispiel

Originalgrammatik:

\begin{displaymath}S\rightarrow A\vert aB\vert aC\end{displaymath}


\begin{displaymath}A\rightarrow B\vert C\vert cAd\end{displaymath}


\begin{displaymath}B\rightarrow S\vert Ba\end{displaymath}


\begin{displaymath}C\rightarrow D\vert c\end{displaymath}


\begin{displaymath}D\rightarrow d\vert dDD\end{displaymath}

Algorithmus Nr. 1: Elimination der Kettenregeln
  1. Wir finden die Kette

    \begin{displaymath}S\rightarrow A\,\,\,\,\,\, A\rightarrow B\,\,\,\,\,\,\, B\rightarrow S\end{displaymath}

    und eliminieren diese, indem wir $A$ und $B$ durch $S$ in den übrigen Regeln ersetzen und diese Regeln streichen. Dabei können wir auch die entstehende Regel $S\rightarrow S$ streichen.
    Wir erhalten

    \begin{displaymath}\begin {array}{llll}S\rightarrow aS\vert aC\vert&\underbrace{... ...}&\vert&\underbrace{Sa}\\ &Aus\,A & &Aus \,B\\ \end {array} \end{displaymath}


    \begin{displaymath}C\rightarrow D\vert c\end{displaymath}


    \begin{displaymath}D\rightarrow d\vert dDD\end{displaymath}

  2. Ersetzung der alleinstehenden Nonterminale
    Wir ersetzen $C\rightarrow D\vert c$ durch

    \begin{displaymath}C\rightarrow d\vert dDD\vert c\end{displaymath}

    und $S\rightarrow aS\vert aC\vert C\vert cSd\vert Sa$ durch

    \begin{displaymath}S\rightarrow aS\vert aC\vert d\vert dDD\vert cSd\vert Sa\end{displaymath}

Von diesem Algorithmus ausgegebene Grammatik ist nun:

\begin{displaymath}S\rightarrow aS\vert aC\vert d\vert dDD\vert cSd\vert Sa\end{displaymath}


\begin{displaymath}C\rightarrow d\vert dDD\vert c\end{displaymath}


\begin{displaymath}D\rightarrow d\vert dDD\end{displaymath}

Erstellung der CNF:
  1. Führe die Elimination der Kettenregeln mit dem obigen Algorithmus durch
  2. Erzeuge für alle Terminale $a\in\Sigma$

    \begin{displaymath}A_{a}\rightarrow a\end{displaymath}

    und ersetze alle Terminale, die nicht alleinstehend sind:

    \begin{displaymath}A_{a}\rightarrow a\end{displaymath}


    \begin{displaymath}A_{c}\rightarrow c\end{displaymath}


    \begin{displaymath}A_{d}\rightarrow d\end{displaymath}


    \begin{displaymath}S\rightarrow A_{a}S\vert A_{a}C\vert d\vert A_{d}DD\vert A_{c}SA_{d}\vert SA_{a}\end{displaymath}


    \begin{displaymath}C\rightarrow d\vert A_{d}DD\vert c\end{displaymath}


    \begin{displaymath}D\rightarrow d\vert A_{d}DD\end{displaymath}

  3. Wir splitten die Regeln mit mehr als 2 Nonterminalen auf der rechten Seite

    $S\rightarrow A_{d}DD$ wird zu

    \begin{displaymath}S\rightarrow A_{d}X_{1}\,\,\,\,\,\,\, X_{1}\rightarrow DD\end{displaymath}

    $S\rightarrow A_{c}SA_{d}$ wird zu

    \begin{displaymath}S\rightarrow A_{c}X_{2}\,\,\,\,\,\,\, X_{2}\rightarrow SA_{d}\end{displaymath}

    $C\rightarrow A_{d}DD$ wird zu

    \begin{displaymath}C\rightarrow A_{d}X_{3}\,\,\,\,\,\,\, X_{3}\rightarrow DD\end{displaymath}

    $D\rightarrow A_{d}DD$ wird zu

    \begin{displaymath}C\rightarrow A_{d}X_{4}\,\,\,\,\,\,\, X_{4}\rightarrow DD\end{displaymath}

Die Ausgabegrammatik ist

\begin{displaymath}A_{a}\rightarrow a\end{displaymath}


\begin{displaymath}A_{c}\rightarrow c\end{displaymath}


\begin{displaymath}A_{d}\rightarrow d\end{displaymath}


\begin{displaymath}S\rightarrow A_{a}S\vert A_{a}C\vert d\vert A_{d}X_{1}\vert A_{c}X_{2}\vert SA_{a}\end{displaymath}


\begin{displaymath}X_{1}\rightarrow DD\end{displaymath}


\begin{displaymath}X_{2}\rightarrow SA_{d}\end{displaymath}


\begin{displaymath}C\rightarrow A_{d}\vert A_{d}X_{3}\vert A_{c}\end{displaymath}


\begin{displaymath}X_{3}\rightarrow DD\end{displaymath}


\begin{displaymath}D\rightarrow A_{d}\vert A_{d}X_{4}\end{displaymath}


\begin{displaymath}X_{4}\rightarrow DD\end{displaymath}

Größe der CNF


\begin{displaymath}size(G_{CNF})\leq size(G_{normal})^{2}\end{displaymath}

Im wesentlichen passiert dies durch die Eliminierung der Kettenregeln.

Fußnoten

... gilt55
Dies läßt sich erledigen, indem man die starken Zusammenhangskomponenten des Digraphen $(V,E)$ (wobei $(A,B)\in E$ genau dann, wenn $A \rightarrow B$) berechnet, den azyklischen Digraphen der starken Zusammenhangskomponenten erstellt und anschließend von diesem eine Topologische Sortierung macht.
Nutzlose Variablen Kontextfreie Sprachen (CFG) CYK-Algorithmus für das Wortproblem