如何将CYK算法应用于此CFG？

Question

假设CFG G为：

S −→ AB|BA|AC|BD|EE
A −→ a
B −→ b
C −→ EB
D −→ EA
E −→ AB|BA|AC|BD|EE

如何使用CYK算法来确定字符串aabbab是否为语言的一部分？

这是我笔记中的伪代码：

  for i in 1 .. n
     V[i,1] = { A | A -> x[i] }
  for j in 2..n
     for i in 1 .. n-j+1
        {
          V[i,j] = phi
          for k in 1 .. j-1
             V[i,j] = V[i,j] union { A | A -> BC where B in V[i,k]
                                                 and   C in V[i+k,j-k]}
        }

但我不明白答案怎么会是倒置的三角形。

例如,

V[i,j]               i
         1(b)   2(a)   3(a)   4(b)   5(a)

      1  B      A,C    A,C    B      A,C

      2  S,A    B      S,C    S,A
  j
      3  phi    B      B

      4  phi    S,A,C

      5  S,A,C
         ^
         |_ accept

Answer 1

伪代码*描述了如何应用算法来创建图表。

[i, j]对引用输入的子字符串，该子字符串从第i个符号开始，扩展到j符号。所以[2, 3]指的是一个3符号子字符串，从符号2开始。如果你的输入是baaba，那么[2, 3]指的是中间的aab。(索引是从1开始的，而不是从0开始。)

图表形成一个三角形，因为您不能有比输入更长的子字符串。如果输入是5个符号，那么你可以在[1, 5]中有一个值，但是你不能有[2, 5]，因为它不再引用一个子字符串。因此，每一行都比它前面的一行短了一个方框，形成了三角形。

V[i, j]指的是图表中的一个框。每个框都是可能生成[i, j]描述的子字符串的非终结符的集合。

该算法依赖于Chomsky范式中的语法。在CNF中，每个产品的右侧要么是一个终端符号，要么是两个非终端符号。(还有另一种算法可以将上下文无关文法转换为CNF。)

基本上，您从输入的所有1符号子字符串开始。伪代码中的第一个循环填充图表的第一行(j == 1)。它查看语法中的所有产生式，如果产生式的右侧对应于该符号，则将该产生式左侧的非终结符添加到集合V[i, 1]。(您的示例的第一行似乎有一些假条目。{A, C}集应该只是{A}。)

然后，该算法继续遍历其余行，查找可以生成相应子字符串的所有可能的结果。对于将当前子字符串一分为二的每种可能方法，它都会查找相应的结果。这包括组合来自前一行上某些盒子的非终端对，并检查是否存在产生该对的任何产品，从而为该盒子构建一组非终端。

如果最后一行中的框以包含开始符号的集合结束，则根据语法，输入是有效的。直观地说，它说开始符号是一个有效的结果，用于生成子字符串，该子字符串从第一个符号开始，一直到整个长度。

*看起来问题中显示的伪代码包含一些转录错误。你会想要咨询一个权威的来源来获得正确的细节。