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 O(n^3) względem długości słowa. Język bezkontekstowy musi być przedstawiony w postaci normalnej Chomsky'ego.

Algorytm[edytuj | edytuj kod]

Pseudokod algorytmu:

Tworzymy tablicę T[i,j,x], dla 1 \leqslant i \leqslant j \leqslant n, 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 X \rightarrow a, 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ę Z \rightarrow XY, ustawiamy T[j,i,Z] := 1
Słowo należy do języka, jeśli T[1,n,S] = 1, gdzie S to symbol startowy gramatyki

Przykład[edytuj | edytuj kod]

Dana jest gramatyka bezkontekstowa w postaci normalnej Chomsky'ego:

[1] S\rightarrow AC
[2] C\rightarrow SB
[3] S\rightarrow AB
[4] A\rightarrow a
[5] B\rightarrow b

Formalnie:

G = \{a^nb^n | n \geqslant 1\}

Pytanie: aabbb \in G?

Inicjalizacja tabeli:

1 2 3 4 5
a a b b b
1
2
3
4
5

Wyrazy długości 1:

pola [1,1] = [1,2] = \{A\}, z racji istnienia reguły [4]
pola [1,3] = [1,4] = [1,5] = \{B\}, z racji istnienia reguły [5]
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2
3
4
5

Wyrazy długości 2:

pole [2,1] = \emptyset, ponieważ nie istnieje żadne reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych AA
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 -
3
4
5
pole [2,2] = \{S\}, z racji produkcji [3]
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\}
3
4
5
pole [2,3] = \emptyset, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych BB
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} -
3
4
5
pole [2,4] = \emptyset, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych BB
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3
4
5

Wyrazy długości 3:

pole [3,1] = \emptyset, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych AS lub tylko B
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 -
4
5
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 -
4
5
pole [3,2] = \{C\}, z racji reguły [2]
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - -
4
5
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\}
4
5
pole [3,3] = \emptyset, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol B
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4
5
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4
5

Wyrazy długości 4:

pole [4,1] = \{S\}, z racji reguły [1]
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\}
5
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 -
5
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 -
5
pole [4,2] = \emptyset, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol A, S lub ciąg symboli nieterminalnych CB.
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\} -
5
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\} -
5
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\} -
5

Wyrazy długości 5:

pole [5,1] = \{C\}, z racji reguły [2]
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\} -
5 -
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\} -
5 -
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\} -
5 -
1 2 3 4 5
a a b b b
1 \{A\} \{A\} \{B\} \{B\} \{B\}
2 - \{S\} - -
3 - \{C\} -
4 \{S\} -
5 \{C\}

Ponieważ symbol startowy S nie jest podzbiorem zbioru w polu [5,1], czyli \{C\}, wyraz aabbb nie jest elementem gramatyki G.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]