CYK算法

CYK算法（英語：Cocke–Younger–Kasami algorithm，縮寫為CYK algorithm）是由約翰·科克，Younger和嵩忠雄（日语：嵩忠雄）共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串${\displaystyle ~w\in \Sigma ^{*}}$ 是否属于一个上下文无关文法的算法。普通的回溯法（backtracking）在最坏的情况下需要指数时间才能解决这样的问题，而CYK算法只需要多项式时间就够了（${\displaystyle ~O(n^{3})}$ ， n 为字符串 w 的长度）。CYK算法采用了动态规划的思想。

对于一个任意给定的上下文无关文法，都可以使用CYK算法来计算上述问题，但首先要将该文法转换成乔姆斯基范式。

• ${\displaystyle ~G=(V,\Sigma ,S,P)}$ 是一个上下文无关文法
• 对于任意字符串 ${\displaystyle w=\sigma _{1}...\sigma _{n}\in \Sigma ^{*}}$ ，定义 ${\displaystyle w[i,j]=\sigma _{i}...\sigma _{j},~1\leq i\leq j\leq n}$
• 对于任意选择的 ${\displaystyle ~i,j}$ ，定义 ${\displaystyle V_{i,j}=\{X\in V~|~X\Rightarrow ^{*}w[i,j]\}}$

通过由下而上的方法计算 ${\displaystyle ~V_{i,j}}$ 这个集合，如果 ${\displaystyle S\in V_{1,n}}$ ，那么就说明 ${\displaystyle ~w}$ 是被上下文无关文法 ${\displaystyle ~G}$ 接受的字符串。

因为 ${\displaystyle ~G}$ 是一个乔姆斯基范式，当且仅当有下面描述的情况时 ${\displaystyle X\in V_{i,j}}$ ：

• ${\displaystyle i<j,~\exists Y,Z,k:X\rightarrow YZ}$ 是 ${\displaystyle ~G}$ 中的一个规则且 ${\displaystyle Y\in V_{i,k},Z\in V_{k+1,j}}$

FOR i:= 1 TO n DO ${\displaystyle V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}}$
FOR l:= 1 TO n-1
    FOR i:= 1 TO n-l DO
        ${\displaystyle ~V_{i,i+l}:=\varnothing }$
        FOR k:= i TO i+l-1 DO
            ${\displaystyle ~V_{i,i+l}:=V_{i,i+l}\cup \{X~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}}$
IF ${\displaystyle S\in V_{1,n}}$ THEN accept ELSE reject

对于上述CYK算法作一个小改动，也就是说记住每次的k，就可以自动产生一个由该上下文无关语言的推导树。

FOR i:= 1 TO n DO ${\displaystyle V_{i,i}:=\{X\in V~|~X\rightarrow \sigma _{i}~in~P\}}$
FOR l:= 1 TO n-1
    FOR i:= 1 TO n-l DO
        ${\displaystyle ~V_{i,i+l}:=\varnothing }$
        FOR k:= i TO i+l-1 DO
            ${\displaystyle ~V_{i,i+l}:=V_{i,i+l}\cup \{(X,k)~|~X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,i+l}\}}$
IF ${\displaystyle \exists k:(S,k)\in V_{1,n}}$ THEN accept ELSE reject

通过对下面的方法递归运行就可以生成推导树。

Tree(X,i,j):
   IF i=j THEN RETURN ${\displaystyle ~\sigma _{i}}$
   选择一个 k 使 ${\displaystyle (X,k)\in V_{i,j}}$
    选择 Y 和 Z 使 ${\displaystyle X\rightarrow YZ,Y\in V_{i,k},Z\in V_{k+1,j}}$
    RETURN Tree(X,Tree(Y,i,k),Tree(Z,k+1,j))

给定一个乔姆斯基范式的上下文无关文法 ${\displaystyle ~G=(\lbrace S,A,B,C\rbrace ,\lbrace a,b\rbrace ,S,P)}$ ，其中规则 P 如下：

${\displaystyle S\rightarrow AB\mid BC}$

${\displaystyle A\rightarrow BA\mid a}$

${\displaystyle B\rightarrow CC\mid b}$

${\displaystyle C\rightarrow AB\mid a}$

问：字符串 bbabaa 能不能通过该文法产生？

CYK算法可以通过一个表格来运算，表中 i 列 j 行表示由哪几个非终结符可以产生字字符串 ${\displaystyle \sigma _{i}\dots \sigma _{j}}$ 。

如果在表格的最左下角一格中有文法的开始非终结符 S ，那么字符串 bbabaa 就能由上面给出文法 G 产生。

• Interaktives Java-Applet zur Demonstration（页面存档备份，存于互联网档案馆）