CYK-Algorithmus für das Wortproblem ::: Theoretische Informatik

Menü

Informatik » Bachelor » Theoretische Informatik » Kontextfreie Sprachen (CFG) » CYK-Algorithmus für das Wortproblem

Chomsky Normalform (CNF) Kontextfreie Sprachen (CFG) Pumping Lemma für kontextfreie Sprachen

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
⁵⁶
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 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 :Spalten und :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})$ ⁵⁷.

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

... ⁵⁶: Die mit $\star$ gekennzeichneten Zellen werden nicht belegt.
... $O(n^{2})$ ⁵⁷: ist die Länge des Eingabewortes

Chomsky Normalform (CNF) Kontextfreie Sprachen (CFG) Pumping Lemma für kontextfreie Sprachen