Algorytm CYK

Algorytm CYK

Algorytm CYK (Cocke’a-Youngera-Kasamiego) to dynamiczny algorytm służący do sprawdzania, czy dane słowo należy do języka bezkontekstowego. Wymaga on, aby język był przedstawiony w normalnej postaci Chomsky’ego. Czas działania algorytmu wynosi $O(n^3\; \backslash cdot\; |G|)$, gdzie $n$ to długość słowa, a $|G|$ to rozmiar gramatyki.

Opis działania algorytmu

Algorytm działa w następujący sposób:

• Tworzenie tablicy $T[i,j,x]$ dla $1\; \backslash leqslant\; i\; \backslash leqslant\; j\; \backslash leqslant\; n$, z inicjalizacją wartości do 0.
• Ustawianie wartości w tablicy dla znaków pojedynczych:
  • Dla znaku $a$ na pozycji $i$ oraz produkcji $X\; \backslash to\; a$, ustawiamy $T[i,1,X]\; :=\; 1$.
• Dla każdej długości $i$ od 2 do $n$:
  • Dla każdego początku $j$ od 1 do $n-i+1$:
  • Dla każdego podziału $k$ od 1 do $i-1$:
    • Jeśli $T[j,k,X]$ i $T[j+k,i-k,Y]$ są ustawione oraz istnieje produkcja $Z\; \backslash to\; XY$, ustawiamy $T[j,i,Z]\; :=\; 1$.
• Słowo należy do języka, jeśli $T[1,n,S]\; =\; 1$, gdzie $S$ to symbol startowy gramatyki.

Przykład zastosowania

Rozważmy gramatykę bezkontekstową w normalnej postaci Chomsky’ego:

• $S\; \backslash to\; AC$
• $C\; \backslash to\; SB$
• $S\; \backslash to\; AB$
• $A\; \backslash to\; a$
• $B\; \backslash to\; b$

Formalnie, język opisany przez gramatykę to: $G\; =\; \backslash \{a^nb^n\; |\; n\; \backslash geqslant\; 1\backslash \}$. Sprawdzamy, czy słowo $aabbb$ należy do tego języka.

Inicjalizacja tabeli

Podczas inicjalizacji tabeli, dla wyrazów długości 1, mamy:

• $[1,1]\; =\; [1,2]\; =\; \backslash \{A\backslash \}$ (reguła [4])
• $[1,3]\; =\; [1,4]\; =\; [1,5]\; =\; \backslash \{B\backslash \}$ (reguła [5])

Dla wyrazów długości 2, wyniki to:

• $[2,2]\; =\; \backslash \{S\backslash \}$ (reguła [3])
• Pozostałe pola są puste, ponieważ nie istnieją odpowiednie reguły.

Kontynuując dla wyrazów długości 3, 4 i 5, końcowy wynik dla długości 5 w polu $[5,1]$ to $\backslash \{C\backslash \}$. Ponieważ symbol startowy $S$ nie znajduje się w tym zbiorze, słowo $aabbb$ nie należy do gramatyki $G$.