所以我一直在阅读维基百科和许多 powerpoints/pdf 中的 CYK algorithm。
在维基百科中,有一部分我不是 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究竟是什么?
编辑:
谢谢大家,我肯定已经学会了如何去做。
希望我能得到你的两个答案作为选定的答案。
最佳答案
当您执行 CYK 算法时,您基本上是从底部到最上面的元素填充底部三角矩阵。每当某个元素 (j,i,x)
其中 j
是列索引, i
是行索引, x
是非终结符时,这意味着您可以从符号 j
生成子序列 j+i-1
到 Rx
的单词。
您的目标是从起始符号之一生成整个单词。与生成整个单词的可能性对应的元素是 (1,n,x)
- 矩阵的最左边和最上面的元素,其中 x
是非终结符的索引。由于您必须从一个开始符号开始,因此您只是在寻找所有非终结符的子集 - s
的子集。如果您设法从一个起始符号生成整个单词,您只需声明该单词是该语言的一部分。如果不存在这样的开始符号,您将无法生成该单词,并且该单词不是语法所描述的语言的一部分。
关于java - CYK算法伪码混淆,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14704473/