Algorytm CYK

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

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

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ż

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