Algoritmus Cocke-Younger-Kasami

Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti $O(n^3)$ vzhledem k délce slova. Bezkontextový jazyk musí být zapsán gramatikou v Chomského normální formě.

Algoritmus vypadá takto:

Vytvoříme pole $T[i,j,x]$, pro $1 \le i \le j \le n$, kde $x$ jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0

Pro každý znak $a$ na pozici $i$, a pro každé $X$ takové, že v gramatice existuje pravidlo $X \rightarrow a$, nastavíme v poli $T[i,1,X] := 1$

Pro každou délku podslova $i$ od 2 do $n$:

Pro každý začátek podslova $j$ od 1 do $n-i+1$:

Pro každou délku první poloviny podslova $k$ od 1 do $i-1$:

Jestliže v poli mají jedničkovou hodnotu $T[j,k,X]$ i $T[j+k,i-k,Y]$, a v gramatice existuje pravidlo $Z \rightarrow XY$, nastavíme v poli $T[j,i,Z] := 1$

Slovo náleží do jazyka, jestliže $T[1,n,S] = 1$, kde $S$ je vstupní neterminál gramatiky.

Související články

• Dynamické programování