CYK算法伪码混淆

Question

所以我一直在维基百科和许多powerpoint/pdf上阅读关于CYK algorithm的文章。

在维基百科中，有一部分我并不是百分之百地理解它想要表达的意思。你们能帮我分析一下吗？

let the input be a string S consisting of n characters: a1 ... an.
let the grammar contain r nonterminal symbols R1 ... Rr.
This grammar contains the subset Rs which is the set of start symbols.
let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
for each i = 1 to n
  for each unit production Rj -> ai
     set P[i,1,j] = true

for each i = 2 to n -- Length of span
 for each j = 1 to n-i+1 -- Start of span
  for each k = 1 to i-1 -- Partition of span
   for each production RA -> RB RC
    if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true

if any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs) then S is member of language
  else
S is not member of language

真正让我困惑的部分是“如果P1，n，x中的任何一个是真的(x在集合s上迭代，其中s是R的所有索引)，那么S是语言的成员，否则S不是语言的成员”。

它是不是说，对于任何存在的n和x，如果它为真，那么它就是一个成员？或者它是说字符串长度n和x，如果为真，那么它是一个成员？或者是完全不同的东西？

还有，X到底是什么？

编辑：

谢谢你们，我确实学会了怎么做。我希望我能得到你的两个答案作为选择的答案。

Answer 1

当您执行CYK算法时，基本上是从底部到最上面的元素填充底部三角形矩阵。当某些元素(j,i,x) (其中j是列索引，i是行索引，x是非终止符号)为真时，这意味着您能够从符号Rx生成单词的子序列j到j+i-1。

您的目标是从一个起始符号生成整个单词。与生成整个单词的可能性相对应的元素是(1,n,x) -矩阵的最左边也是最上面的元素，其中x是非终结符的索引。因为您必须从一个开始符号开始，所以您只需查找所有非终结符的子集-- s的子集。如果您设法从其中一个开始符号生成整个单词，则只需声明该单词是该语言的一部分。如果不存在这样的起始符号，则无法生成该单词，并且该单词不是语法所描述的语言的一部分。

Answer 2

在这个算法中，Pa，b，c = true意味着从索引a开始且长度为b的词法标记的子串可以被解析为非终结符c。