CYK算法

CYK算法（英语：Cocke–Younger–Kasami algorithm，缩写为CYK algorithm）是由约翰·科克，Younger和嵩忠雄（日语：嵩忠雄）共同研究出来大约发表于1965年的一个算法，它是一个用来判定任意给定的字符串${\displaystyle w\in <!--\; \in \; -->{\mathrm{\Sigma <!--\; \Sigma \; -->}}^{\ast <!--\; \ast \; -->}}$ i:= 1 n ${\displaystyle V_{i,i}:=\{X\in <!--\; \in \; -->V|X\to <!--\; \to \; -->{\mathrm{\sigma <!--\; \sigma \; -->}}_{i}inP\}}$ l:= 1 n-1 i:= 1 n-l ${\displaystyle V_{i,i+l}:=\mathrm{\varnothing <!--\; \varnothing \; -->}}$ k:= i i+l-1 ${\displaystyle V_{i,i+l}:=V_{i,i+l}\cup <!--\; \cup \; -->\{X|X\to <!--\; \to \; -->YZ,Y\in <!--\; \in \; -->V_{i,k},Z\in <!--\; \in \; -->V_{k+1,i+l}\}}$ ${\displaystyle S\in <!--\; \in \; -->V_{1,n}}$ accept reject

扩展CYK算法

简介

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

 i:= 1  n  ${\displaystyle V_{i,i}:=\{X\in <!--\; \in \; -->V|X\to <!--\; \to \; -->{\mathrm{\sigma <!--\; \sigma \; -->}}_{i}inP\}}$ l:= 1  n-1     i:= 1  n-l         ${\displaystyle V_{i,i+l}:=\mathrm{\varnothing <!--\; \varnothing \; -->}}$ k:= i  i+l-1             ${\displaystyle V_{i,i+l}:=V_{i,i+l}\cup <!--\; \cup \; -->\{(X,k)|X\to <!--\; \to \; -->YZ,Y\in <!--\; \in \; -->V_{i,k},Z\in <!--\; \in \; -->V_{k+1,i+l}\}}$ ${\displaystyle \mathrm{\exists <!--\; \exists \; -->}k:(S,k)\in <!--\; \in \; -->V_{1,n}}$ accept  reject

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

Tree(X,i,j):    i=j  RETURN ${\displaystyle {\mathrm{\sigma <!--\; \sigma \; -->}}_i}$   选择一个 k 使 ${\displaystyle (X,k)\in <!--\; \in \; -->V_{i,j}}$    选择 Y 和 Z 使 ${\displaystyle X\to <!--\; \to \; -->YZ,Y\in <!--\; \in \; -->V_{i,k},Z\in <!--\; \in \; -->V_{k+1,j}}$    RETURN Tree(X,Tree(Y,i,k),Tree(Z,k+1,j))

例子

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

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

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

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