Algoritmus CYK (Cocke-Younger-Kasami) je algoritmus, který určuje, zda slovo náleží do bezkontextového jazyka, a to v časové složitosti 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 , pro , kde jsou postupně všechny neterminály (nebo alternativně jejich čísla), a hodnoty všech jeho prvků nastavíme na 0
- Pro každý znak na pozici , a pro každé takové, že v gramatice existuje pravidlo , nastavíme v poli
- Pro každou délku podslova od 2 do :
- Pro každý začátek podslova od 1 do :
- Pro každou délku první poloviny podslova od 1 do :
- Jestliže v poli mají jedničkovou hodnotu i , a v gramatice existuje pravidlo , nastavíme v poli
- Slovo náleží do jazyka, jestliže , kde je vstupní neterminál gramatiky.
Jiné algoritmy jsou Earlyho parser a packrat parser.
Související články
Zdroj
Poslední aktualizace obsahu: 2024-04-03 04:54:49
Zdroj: Wikipedia (autoři článku Algoritmus Cocke-Younger-Kasami)
Licence textu: CC-BY-SA-3.0 Unported
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.