CYK算法伪代码混淆

Question

我一直在阅读维基百科和许多幻灯片/PDF文档中关于CYK算法的内容。

维基百科中有一个部分，我不确定它想表达什么。你们能帮我梳理一下吗？

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

我最困惑的部分是：“如果任何P [1，n，x]为真（其中x在集合s上迭代，其中s是Rs的所有索引），则S是语言的成员，否则S不是语言的成员”

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

另外，X到底是什么？

编辑：

谢谢大家，我肯定学会如何做了。 希望我能得到你们两个的答案作为被选答案。

- Kelsey Abreu

Answer 1

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

您的目标是从一个起始符号生成整个单词。对应于生成整个单词的可能性的元素是 (1,n,x) - 矩阵的最左上角的元素，其中x是您的非终端符号的索引。由于您必须从其中一个起始符号开始，因此只需寻找您所有非终端符号的子集 - 子集s。如果您能够从其中一个起始符号生成整个单词，则简单地声明该单词是语言的一部分。如果不存在这样的起始符号，则无法生成该单词，该单词也不属于文法所描述的语言。

- Karel Horak

Answer 2

它的意思是，如果对于任何起始非终端x，P[1,n,x]为真，则整个字符串（从1到n的词法标记）可以解析为非终端x。在此算法中，P[a,b,c]=true表示以索引a开始且长度为b的词法标记子字符串可以解析为非终端c。

- Antti Huima