CYK-Algorithmus

Gute Seite zum verstehen des CYK

CYK-Algorithmus

Kurzerklärung

Der CYK-Algorithmus (Cocke-Younger-Kasami-Algorithmus) ist ein Parsing-Algorithmus für kontextfreie Grammatiken, der zur Überprüfung verwendet wird, ob eine gegebene Zeichenkette zu einer bestimmten kontextfreien Sprache gehört. Er funktioniert durch dynamische Programmierung und arbeitet in der Chomsky-Normalform.

In der Theorie der formalen Sprachen wird der CYK-Algorithmus typischerweise wie folgt beschrieben:

Voraussetzungen

Bevor der CYK-Algorithmus angewendet werden kann, muss die kontextfreie Grammatik in Chomsky-Normalform (CNF) vorliegen. Eine Grammatik ist in CNF, wenn jede Produktionsregel eine der folgenden Formen hat:

1. $A\to BC$ (wobei $A,B,C$ Nichtterminale sind)
2. $A\to a$ (wobei $A$ ein Nichtterminal und $a$ ein Terminal ist)
3. $S\to ϵ$ (wobei $S$ das Startsymbol ist und $ϵ$ das leere Wort)

CYK-Algorithmus

Der CYK-Algorithmus wird in drei Hauptschritten durchgeführt:

1. Initialisierung:

   • Erstelle eine Tabelle $T$ der Größe $n\times n$, wobei $n$ die Länge der Eingabezeichenkette ist.
   • Fülle die Diagonale der Tabelle mit den Nichtterminalen, die die jeweiligen Terminale ableiten.

2. Rekursion:

   • Fülle die Tabelle von der unteren linken Ecke bis zur oberen rechten Ecke, indem du überprüfst, ob die Kombinationen der Einträge in den unteren Dreiecken der Tabelle durch die Produktionsregeln abgeleitet werden können.

3. Akzeptanz:

   • Überprüfe, ob das Startsymbol $S$ in der oberen rechten Ecke der Tabelle enthalten ist. Wenn ja, gehört die Eingabezeichenkette zur Sprache der Grammatik.

---

CYK-Algorithmus anwenden

Ablauf zur Anwendung des CYK-Algorithmus

1. Konvertieren Sie die Grammatik in Chomsky-Normalform (CNF): Stellen Sie sicher, dass die gegebene Grammatik in CNF vorliegt.
2. Initialisierung der Tabelle: Erstellen Sie eine Tabelle $T$ mit der Größe $n\times n$, wobei $n$ die Länge der Eingabezeichenkette ist.
3. Füllen der Diagonale: Füllen Sie die Diagonale der Tabelle mit den Nichtterminalen, die die entsprechenden Terminale ableiten.
4. Füllen der restlichen Tabelle: Verwenden Sie die Produktionsregeln, um die restlichen Zellen der Tabelle zu füllen. Kombinieren Sie die Einträge gemäß der Produktionsregeln.
5. Überprüfung: Überprüfen Sie, ob das Startsymbol in der oberen rechten Ecke der Tabelle enthalten ist. Wenn ja, gehört das Wort zur Sprache.

Beispiel zur Anwendung des CYK-Algorithmus auf w_1 = \#$##[[FSK-ÜB-6#FSK6-2 CYK-Algorithmus (2 Punkte)#ii)w_2 = ]]

Aufgabenstellung

Sei $G$ die Grammatik ({A_1, A_2, A_3, A_4, A_5}, \{\, #}, P, A_1)$ mit

$$\begin{array}{rl}P=\{& A_1\to A_3{A}_4\mid A_3{A}_2,\\ & A_2\to A_2{A}_3\mid A_4{A}_4,\\ & A_3\to \$,\\ & A_4\to \#\mid A_3{A}_4,\\ & A_5\to A_4{A}_4\mid \#\}\end{array}$$

ii) w_2 = \$$##$

Gegebene Grammatik $G$:

$$\begin{array}{rl}P=\{& A_1\to A_3{A}_4\mid A_3{A}_2,\\ & A_2\to A_2{A}_3\mid A_4{A}_4,\\ & A_3\to \$,\\ & A_4\to \#\mid A_3{A}_4,\\ & A_5\to A_4{A}_4\mid \#\}\end{array}$$

Eingabewort: w_2 = \$$##$

Schritt 1: Initialisierung der Tabelle

$$\begin{array}{ccccc}1& 2& 3& 4& 5\\ \$& \$& \$& \#& \#\\ A_3& A_3& A_3& A_4,A_5& A_4,A_5\end{array}$$

Schritt 2: Rekursion

$V_{i,j}$	1	2	3	4	5
1	$A_3$	$A_3$	$A_3$	$A_4,A_5$	$A_4,A_5$
2			$A_1,A_4$	$A_2,A_5$	-
3		$A_1,A_4$	$A_1,A_2,A_5$	-	-
4	$A_1,A_4$	$A_1,A_2,A_5$	-	-	-
5	$A_1,A_2,A_5$	-	-	-	-

Zeile 2:

• $V_{1,2}$ = $(V_{1,1}\times V_{2,1})=A_3{A}_3⟹\varnothing$
• $V_{2,2}$ = $(V_{2,1}\times V_{3,1})=A_3{A}_3⟹\varnothing$
• $V_{3,2}$ = $(V_{3,1}\times V_{4,1})=A_3{A}_4,A_3{A}_5\stackrel{A_3{A}_4}{⟹}{A}_1,A_4$
• $V_{4,2}$ = $(V_{4,1}\times V_{5,1})=A_4{A}_4,A_4{A}_5,A_5{A}_4,A_5{A}_5\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Zeile 3:

• $V_{1,3}=\varnothing$

  • $V_{1,1}\times V_{2,2}=A_3\times \varnothing ⟹\varnothing$
  • $V_{1,2}\times V_{3,2}=\varnothing \times A_3⟹\varnothing$

• $V_{2,3}=A_1,A_4$

  • $V_{2,1}\times V_{3,2}=A_3\times A_1,A_4=A_3{A}_1,A_3{A}_4\stackrel{A_3{A}_4}{⟹}{A}_1,A_4$
  • $V_{4,1}\times V_{2,2}=A_4{A}_5\times \varnothing ⟹\varnothing$

• $V_{3,3}=A_1,A_2,A_5$

  • $V_{3,1}\times V_{4,2}=A_3\times A_2,A_5=A_3{A}_2,A_3{A}_5\stackrel{A_3{A}_2}{⟹}{A}_1$
  • $V_{5,1}\times V_{3,2}=A_4{A}_5\times A_1,A_4=A_4{A}_1,A_4{A}_4,A_5{A}_1,A_5{A}_4\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Zeile 4:

• $V_{1,4}=A_1,A_4$

  • $V_{1,1}\times V_{2,3}=A_3\times A_1,A_4=A_3{A}_1,A_3{A}_4\stackrel{A_3{A}_4}{⟹}{A}_1,A_4$
  • $V_{1,2}\times V_{3,2}=\varnothing \times A_1,A_4⟹\varnothing$
  • $V_{1,3}\times V_{4,2}=\varnothing \times A_4,A_5⟹\varnothing$

• $V_{2,4}=A_1,A_2,A_5$

  • $V_{2,1}\times V_{3,3}=A_3\times A_1,A_2,A_5=A_3{A}_1,A_3{A}_2,A_3{A}_5\stackrel{A_3{A}_2}{⟹}{A}_1$
  • $V_{2,2}\times V_{4,2}=\varnothing \times A_2,A_5⟹\varnothing$
  • $V_{2,3}\times V_{5,1}=A_1,A_4\times A_4,A_5=A_1{A}_4,A_1{A}_5,A_4{A}_4,A_4{A}_5\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Zeile 5:

• $V_{1,5}=A_1,A_2,A_5$
  • $V_{1,1}\times V_{2,4}=A_3\times A_1,A_2,A_5=A_3{A}_1,A_3{A}_2,A_3{A}_5\stackrel{A_3{A}_2}{⟹}{A}_1$
  • $V_{1,2}\times V_{3,3}=\varnothing \times A_1,A_2,A_5⟹\varnothing$
  • $V_{1,3}\times V_{4,2}=\varnothing \times A_2,A_5⟹\varnothing$
  • $V_{1,4}\times V_{5,1}=A_1,A_4\times A_4,A_5=A_1{A}_4,A_1{A}_5,A_4{A}_4,A_4,A_5\stackrel{A_4{A}_4}{⟹}{A}_2,A_5$

Fazit:

• Das Wort w_1 = \#$##$istin$L(G)$,daStartsymbol$A_{1} \in V_{1,5}$

---

Algorithmus zur Worterkennung in einer kontextfreien Grammatik

Eingabe

• Kontextfreie Grammatik $G=(V,\Sigma ,P,S)$ in CNF
• Wort $w=a_1,\dots ,a_n\in {\Sigma }^{\ast }$

Ausgabe

• Ja, wenn $w\in L(G)$
• Nein, wenn $w\notin L(G)$

Beginn

• Für $i=1$ bis $n$ tue
  • $V_i=\{A\in V\mid A\to a_i\in P\}$
• Ende
• Für $j=2$ bis $n$ tue
  • Für $i=1$ bis $n+1-j$ tue
    • Für $k=1$ bis $j-1$ tue
      • $V_{i,j}=V_{i,j}\cup \{A\in V\mid A\to BC\in P,B\in V_{i,k},C\in V_{i+k,j-k}\}$
    • Ende
  • Ende
• Ende
• Wenn $S\in V_{1,n}$ dann Rückgabe Ja;
• Sonst Rückgabe Nein;

Ende

Fazit

Der CYK-Algorithmus ist ein effizienter Parsing-Algorithmus für kontextfreie Grammatiken in Chomsky-Normalform. Durch die dynamische Programmierung kann er in $O(n^3\cdot |G|)$-Zeit überprüft werden, ob eine Zeichenkette zu einer gegebenen kontextfreien Sprache gehört, wobei $n$ die Länge der Zeichenkette und $|G|$ die Anzahl der Produktionsregeln der Grammatik ist.

---