Algorytm CYK

Algorytm CYK

Algorytm CYK (Cocke’a-Youngera-Kasamiego) to dynamiczna metoda, która weryfikuje, czy dane słowo należy do języka bezkontekstowego. Język ten musi być zapisany w normalnej postaci Chomskiego. Czas działania algorytmu wynosi

O(n3 ⋅ |G|),

gdzie n to długość słowa, a |G| oznacza rozmiar gramatyki.

Algorytm

Pseudokod algorytmu:

Tworzymy tablicę T[i, j, x], dla 1 ≤ i ≤ j ≤ n, gdzie x przechodzi przez wszystkie nieterminale (lub ich numery), ustawiając wszystkie jej wartości na 0.

Dla każdego znaku a na pozycji i, i dla każdego X, który w gramatyce spełnia produkcję X → 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] oraz T[j + k, i − k, Y], a w gramatyce mamy produkcję Z → 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

Rozważmy gramatykę bezkontekstową w normalnej postaci Chomskiego:

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

Formalnie:

G = {anbn | n ≥ 1}

Pytanie: aabbb ∈ G?

Inicjalizacja tabeli:

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]

Wyrazy długości 2:

pole [2, 1] = ∅, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych AA.

pole [2, 2] = {S}, z racji produkcji [3]

pole [2, 3] = ∅, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych BB.

pole [2, 4] = ∅, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych BB.

Wyrazy długości 3:

pole [3, 1] = ∅, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych AS lub tylko B.

pole [3, 2] = {C}, z racji reguły [2]

pole [3, 3] = ∅, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol B.

Wyrazy długości 4:

pole [4, 1] = {S}, z racji reguły [1]

pole [4, 2] = ∅, ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol A, S lub ciąg symboli nieterminalnych CB.

Wyrazy długości 5:

pole [5, 1] = {C}, z racji reguły [2]. Ponieważ symbol startowy S nie jest podzbiorem zbioru w polu [5, 1], czyli {C}, wyraz aabbb nie jest elementem gramatyki G.

Zobacz też

algorytm Earleya

Bibliografia

John E. Hopcroft: Wprowadzenie do teorii automatów, języków i obliczeń. Warszawa: Wydawnictwo Naukowe PWN, 2005, s. 276. ISBN 83-01-14502-1.

Przeczytaj u przyjaciół: