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\to 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\to 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.

Jiné algoritmy jsou Earlyho parser a packrat parser.

Související články

• Dynamické programování