Przejdź do zawartości

Algorytm CYK

Z Wikipedii, wolnej encyklopedii
Struktura danych

Napis (ciąg znaków)

Złożoność
Czasowa

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 Chomskiego. Algorytm działa w czasie gdzie jest długością słowa, a jest rozmiarem gramatyki.

Algorytm

[edytuj | edytuj kod]

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 | edytuj kod]

Dana jest gramatyka bezkontekstowa w postaci normalnej Chomskiego:

[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 | edytuj kod]

Bibliografia

[edytuj | edytuj kod]