Algoritmus Cocke-Younger-Kasami

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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[editovat | editovat zdroj]