wilhelm büchner_728x90_bachelor_informatik
  Home     
    
    Bücher   Links   Impressum

next up previous contents
Nächste Seite: Pumping Lemma für kontextfreie Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: Chomsky Normalform (CNF)   Inhalt

Unterabschnitte

CYK-Algorithmus für das Wortproblem

Algorithmus

Der CYK-Algorithmus benutzt das Grundprinzip des dynamischen Programmierens. Die CFG muß dabei in CNF vorhanden sein.
  • Wir erstellen eine Tabelle für den Algorithmus in folgender Form
    56
  • Die unterste Zeile der Tabelle füllen wir auf, indem wir Regeln $Nonterminal\rightarrow Terminal$ aus der CNF benutzten.
  • Wir füllen die einzelnen Zellen der Tabelle auf, indem wir für $v[i,j]$ folgende Regel anwenden:

    \begin{displaymath}\begin {array}{ccccc} v[i,j]=\bigcup^{j-1}_{l=1}\{A\in V:\ex... ...i+l,j-l]}&\}\\ &in\,der\,Spalte&&die\,Diagonale&\\ \end{array}\end{displaymath}

    wobei $i$:Spalten und $j$:Zeilen.
  • Wenn $S\in v[1,n]$, so ist $w\in L_{CNF}$.

Laufzeit

Der Algorithmus läuft in der Laufzeit $O(n^{3})$ und hat einen Platzbedarf von $O(n^{2})$57.

Beispiele

Grammatik in CNF:

\begin{displaymath}S\rightarrow AC\vert AB\end{displaymath}


\begin{displaymath}C\rightarrow SB\end{displaymath}


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


\begin{displaymath}B\rightarrow b\end{displaymath}

Für das Wort $w_{1}=aabb$ wird die Tabelle wie folgt von unten nach oben aufgebaut:
$\{S\}$      
$\{\}$ $\{C\}$    
$\{\}$ $\{S\}$ $\{\}$  
$\{A\}$ $\{A\}$ $\{B\}$ $\{B\}$
a a b b
Für das Wort $w_{2}=aaabbb$ wird die Tabelle wie folgt von unten nach oben aufgebaut:
$\{S\}$          
$\{\}$ $\{C\}$        
$\{\}$ $\{S\}$ $\{\}$      
$\{\}$ $\{\}$ $\{C\}$ $\{\}$    
$\{\}$ $\{\}$ $\{S\}$ $\{\}$ $\{\}$  
$\{A\}$ $\{A\}$ $\{A\}$ $\{B\}$ $\{B\}$ $\{B\}$
a a a b b b
Beide Wörter sind in der Sprache enthalten.

Fußnoten

... 56
Die mit $\star$ gekennzeichneten Zellen werden nicht belegt.
...$O(n^{2})$57
$n$ ist die Länge des Eingabewortes
next up previous contents
Nächste Seite: Pumping Lemma für kontextfreie Aufwärts: Kontextfreie Sprachen (CFG) Vorherige Seite: Chomsky Normalform (CNF)   Inhalt