Algorytm CYK

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

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

Algorytm

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\to a,$ ustawiamy w tablicy $T[i,1,X]:=1$

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

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

Dla każdego podziału $\color {Apricot}{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\to 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

Dana jest gramatyka bezkontekstowa w postaci normalnej Chomsky’ego:

[1] $S\to AC$

[2] $C\to SB$

[3] $S\to AB$

[4] $A\to a$

[5] $B\to b$

Formalnie:

$G=\{a^{n}b^{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ż

• 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.