Algorytm CYK

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.

Struktura danych Napis (ciąg znaków)
Złożoność
Czasowa

AlgorytmEdytuj

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  
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  
Słowo należy do języka, jeśli   gdzie   to symbol startowy gramatyki

PrzykładEdytuj

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  
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 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  
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  

Zobacz teżEdytuj

BibliografiaEdytuj