CYK演演算法
約翰·科克等研究出來的演演算法
CYK演演算法（英語：Cocke–Younger–Kasami algorithm，縮寫為CYK algorithm）是由約翰·科克，Younger和嵩忠雄共同研究出來大約發表於1965年的一個演演算法，它是一個用來判定任意給定的字元串 是否屬於一個上下文無關文法的演演算法。
普通的回溯法（backtracking）在最壞的情況下需要指數時間才能解決這樣的問題，而CYK演演算法只需要多項式時間就夠了（{\displaystyle ~}， n 為字元串 w 的長度）。CYK演演算法採用了動態規劃的思想。
對於一個任意給定的上下文無關文法，都可以使用CYK演演算法來計算上述問題，但首先要將該文法轉換成喬姆斯基範式。
1. 是一個上下文無關文法
2.對於任意字元串 ，定義
3. 對於任意選擇的i，j，定義
簡介
通過由下而上的方法計算這個集合，如果，那麼就說明 是被上下文無關文法G接受的字元串。
因為G是一個喬姆斯基範式，當且僅當有下面描述的情況時 ：
是G中的一個規則且
偽代碼
擴展CYK演演算法
簡介
對於上述CYK演演算法作一個小改動，也就是說記住每次的k，就可以自動產生一個由該上下文無關語言的推導樹。
偽代碼