Algoritmus Cocke-Younger-Kasami
Kategorie: Nezařazeno (celkem: 23179 referátů a seminárek)
Informace o referátu:
- Přidal/a: anonymous
- Datum přidání: 11. srpna 2008
- Zobrazeno: 1363×
- Licence: GNU Free Documentation License
- Seznam autorů a změn
- Vyloučení odpovědnosti
Příbuzná témata
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(n3) 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
, 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
, 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
, nastavíme v poli T[j,i,Z]: = 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
- Pro každou délku první poloviny podslova k od 1 do i - 1:
- Pro každý začátek podslova j od 1 do n - i + 1:
- Slovo náleží do jazyka, jestliže T[1,n,S] = 1, kde S je vstupní neterminál gramatiky.