algorithm - 如何将 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] 中有一个值，因为那样不会t 不再引用子字符串。所以每一行都比前一行短一个框，形成三角形。

V[i, j] 指的是图表中的一个方框。每个框都是一组非终结符，它们可能产生了 [i, j] 描述的子字符串。

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

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

算法然后继续遍历其余行，寻找所有可能产生相应子串的产生式。对于将当前子串一分为二的每种可能方式，它都会寻找相应的产生式。这涉及组合来自前几行某些框的非终结符对，并检查是否有任何产生式产生该对，从而为该框构建一组非终结符。

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

[*] 看起来问题中显示的伪代码包含一些转录错误。您需要咨询权威来源以获得正确的详细信息。