Algorytm CYK

Struktura danych	Napis (ciąg znaków)
Złożoność
Czasowa	${\displaystyle O(n^{3}\cdot |G|)}$

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 ${\displaystyle O(n^{3}\cdot |G|),}$ gdzie ${\displaystyle n}$ jest długością słowa, a ${\displaystyle |G|}$ jest rozmiarem gramatyki.

Algorytm

Pseudokod algorytmu:

Tworzymy tablicę ${\displaystyle T[i,j,x],}$ dla ${\displaystyle 1\leqslant i\leqslant j\leqslant n,}$ zaś ${\displaystyle x}$ przebiega wszystkie nieterminale (czy też równoważnie ich numery), wszystkie jej wartości ustawiając na 0

Dla każdego znaku ${\displaystyle a}$ na pozycji ${\displaystyle i,}$ i dla każdego ${\displaystyle X}$ takiego, że w gramatyce jest produkcja ${\displaystyle X\to a,}$ ustawiamy w tablicy ${\displaystyle T[i,1,X]:=1}$

Dla każdej długości ${\displaystyle \color {blue}{i}}$ od 2 do ${\displaystyle n{:}}$

Dla każdego początku ${\displaystyle \color {Green}{j}}$ od 1 do ${\displaystyle n-i+1{:}}$

Dla każdego podziału ${\displaystyle \color {Apricot}{k}}$ od 1 do ${\displaystyle i-1{:}}$

Jeśli w tablicy są ustawione ${\displaystyle T[j,k,X]}$ i ${\displaystyle T[j+k,i-k,Y],}$ a w gramatyce mamy produkcję ${\displaystyle Z\to XY,}$ ustawiamy ${\displaystyle T[j,i,Z]:=1}$

Słowo należy do języka, jeśli ${\displaystyle T[1,n,S]=1,}$ gdzie ${\displaystyle S}$ to symbol startowy gramatyki

Przykład

Dana jest gramatyka bezkontekstowa w postaci normalnej Chomsky’ego:

[1] ${\displaystyle S\to AC}$

[2] ${\displaystyle C\to SB}$

[3] ${\displaystyle S\to AB}$

[4] ${\displaystyle A\to a}$

[5] ${\displaystyle B\to b}$

Formalnie:

${\displaystyle G=\{a^{n}b^{n}|n\geqslant 1\}}$

Pytanie: ${\displaystyle 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 ${\displaystyle [1,1]=[1,2]=\{A\},}$ z racji istnienia reguły [4]

pola ${\displaystyle [1,3]=[1,4]=[1,5]=\{B\},}$ z racji istnienia reguły [5]

	1	2	3	4	5
	a	a	b	b	b
1	${\displaystyle \{A\}}$	${\displaystyle \{A\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$
2
3
4
5

Wyrazy długości 2:

pole ${\displaystyle [2,1]=\emptyset ,}$ ponieważ nie istnieje żadne reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych ${\displaystyle AA}$

	1	2	3	4	5
	a	a	b	b	b
1	${\displaystyle \{A\}}$	${\displaystyle \{A\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$
2	–
3
4
5

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

	1	2	3	4	5
	a	a	b	b	b
1	${\displaystyle \{A\}}$	${\displaystyle \{A\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$
2	–	${\displaystyle \{S\}}$
3
4
5

pole ${\displaystyle [2,3]=\emptyset ,}$ ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych ${\displaystyle BB}$

	1	2	3	4	5
	a	a	b	b	b
1	${\displaystyle \{A\}}$	${\displaystyle \{A\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$
2	–	${\displaystyle \{S\}}$	–
3
4
5

pole ${\displaystyle [2,4]=\emptyset ,}$ ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie ciąg symboli nieterminalnych ${\displaystyle BB}$

	1	2	3	4	5
	a	a	b	b	b
1	${\displaystyle \{A\}}$	${\displaystyle \{A\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$	${\displaystyle \{B\}}$
2	–	${\displaystyle \{S\}}$	–	–
3
4
5

Wyrazy długości 3:

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

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – 4 5

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – 4 5

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

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – – 4 5

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ 4 5

pole ${\displaystyle [3,3]=\emptyset ,}$ ponieważ nie istnieje żadna reguła, która miałaby po prawej stronie symbol ${\displaystyle B}$

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 5

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 5

Wyrazy długości 4:

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

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ 5

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 – 5

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 – 5

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

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ – 5

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ – 5

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ – 5

Wyrazy długości 5:

pole ${\displaystyle [5,1]=\{C\},}$ z racji reguły ${\displaystyle [2]}$

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ – 5 –

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ – 5 –

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ – 5 –

1 2 3 4 5 a a b b b 1 ${\displaystyle \{A\}}$ ${\displaystyle \{A\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ ${\displaystyle \{B\}}$ 2 – ${\displaystyle \{S\}}$ – – 3 – ${\displaystyle \{C\}}$ – 4 ${\displaystyle \{S\}}$ – 5 ${\displaystyle \{C\}}$

Ponieważ symbol startowy ${\displaystyle S}$ nie jest podzbiorem zbioru w polu ${\displaystyle [5,1],}$ czyli ${\displaystyle \{C\},}$ wyraz ${\displaystyle aabbb}$ nie jest elementem gramatyki ${\displaystyle 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.