3

所以我一直在阅读维基百科和许多 powerpoints/pdf 中的CYK 算法。

在维基百科中，有一部分我不是 100% 想要说的。你们能帮我分解一下吗？

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究竟是什么？

编辑：

谢谢大家，我确实学会了怎么做。希望我能将您的两个答案都作为选定的答案。

4

2 回答 2

3

当您执行 CYK 算法时，您基本上是从底部到最上面的元素填充底部三角矩阵。每当列索引、(j,i,x)行索引和非终结符号的某个元素为真时，这意味着您可以从符号生成单词的子序列。jixjj+i-1Rx

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

于 2013-02-05T10:09:46.360 回答
1

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

于 2013-02-05T10:03:42.867 回答