Z Wikipedii, wolnej encyklopedii
Algorytm CYK (Cocke’a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky’ego. Algorytm działa w czasie
gdzie
jest długością słowa, a
jest rozmiarem gramatyki.
Pseudokod algorytmu:
- Tworzymy tablicę
dla
zaś
przebiega wszystkie nieterminale (czy też równoważnie ich numery), wszystkie jej wartości ustawiając na 0
- Dla każdego znaku
na pozycji
i dla każdego
takiego, że w gramatyce jest produkcja
ustawiamy w tablicy ![T[i,1,X]:=1](https://wikimedia.org/api/rest_v1/media/math/render/svg/c2a121ea944edc80b56feae1d61f1fb797d46411)
- Dla każdej długości
od 2 do
- Dla każdego początku
od 1 do
- Dla każdego podziału
od 1 do
- Jeśli w tablicy są ustawione
i
a w gramatyce mamy produkcję
ustawiamy ![T[j,i,Z]:=1](https://wikimedia.org/api/rest_v1/media/math/render/svg/37faad27c09b12c93f689616b6949c6710ca08a3)
- Słowo należy do języka, jeśli
gdzie
to symbol startowy gramatyki
Dana jest gramatyka bezkontekstowa w postaci normalnej Chomsky’ego:
- [1]

- [2]

- [3]

- [4]

- [5]

Formalnie:

Pytanie:
?
Inicjalizacja tabeli:
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
|
|
|
|
|
2 |
|
|
|
|
3 |
|
|
|
4 |
|
|
5 |
|
Wyrazy długości 1:
- pola
z racji istnienia reguły [4]
- pola
z racji istnienia reguły [5]
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
|
|
|
|
3 |
|
|
|
4 |
|
|
5 |
|
Wyrazy długości 2:
- pole
ponieważ nie istnieje żadne reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych 
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
|
|
|
3 |
|
|
|
4 |
|
|
5 |
|
- pole
z racji produkcji [3]
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
|
|
3 |
|
|
|
4 |
|
|
5 |
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych 
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
|
3 |
|
|
|
4 |
|
|
5 |
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych 
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
|
|
|
4 |
|
|
5 |
|
Wyrazy długości 3:
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych
lub tylko 
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
|
|
4 |
|
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
|
|
4 |
|
|
5 |
|
|
- pole
z racji reguły ![[2]](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa32363c093f4cfd50ecba68068bcfd396ea8bff)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
– |
|
4 |
|
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
|
4 |
|
|
5 |
|
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol 
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
|
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
|
|
5 |
|
|
Wyrazy długości 4:
- pole
z racji reguły ![[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/83021ecdd7307a04dbb7873affcaac031e7e935a)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
– |
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
– |
|
5 |
|
|
- pole
ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol
lub ciąg symboli nieterminalnych 
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
–
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
–
|
5 |
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
–
|
5 |
|
|
Wyrazy długości 5:
- pole
z racji reguły ![[2]](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa32363c093f4cfd50ecba68068bcfd396ea8bff)
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
–
|
5 |
–
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
–
|
5 |
–
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
–
|
5 |
–
|
|
|
1 |
2 |
3 |
4 |
5
|
|
a |
a |
b |
b |
b
|
1 |
 |
 |
 |
 |
|
2 |
– |
 |
– |
–
|
3 |
– |
 |
–
|
4 |
 |
–
|
5 |
|
|
Ponieważ symbol startowy
nie jest podzbiorem zbioru w polu
czyli
wyraz
nie jest elementem gramatyki