Algorytm CYK

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Algorytm CYK (Cocke'a-Youngera-Kasamiego) – dynamiczny algorytm sprawdzający, czy słowo należy do języka bezkontekstowego. Algorytm działa w czasie względem długości słowa. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky'ego.

Algorytm[edytuj]

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ład[edytuj]

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]

Bibliografia[edytuj]