Algorytm CYK
Z Wikipedii
Algorytm CYK (Cocke-Younger-Kasami) to algorytm sprawdzania czy słowo należy do języka bezkontekstowego w czasie O(n3) wględem długości słowa. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky'ego.
Algorytm wygląda tak:
- Tworzymy tablicę T[i,j,x], dla
, zaś x przebiega wszystkie nieterminale (czy też równoważnie ich numery), wszystkie jej wartości ustawiając na 0 - Dla każdego znaku a na pozycji i, i dla każdego X takiego, że w gramatyce jest produkcja
, ustawiamy w tablicy 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 w tablicy są ustawione T[j,k,X] i T[j + k,i − k,Y], a w gramatyce mamy produkcję
, ustawiamy T[j,i,Z]: = 1
- Jeśli w tablicy są ustawione T[j,k,X] i T[j + k,i − k,Y], a w gramatyce mamy produkcję
- Dla każdego podziału k od 1 do i − 1:
- Dla każdego początku j od 1 do n − i + 1:
- Słowo należy do języka, jeśli T[1,n,S] = 1, gdzie S to symbol startowy gramatyki
