5

我正在阅读有关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

这些部分是我感到困惑的：

    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

有人会对这些伪代码给出一些提示吗？

4

1 回答 1

3

伪代码

对于每个产生式 R A → R B R C：

如果 P[j,k,B] 和 P[j+k,ik,C] 则设置 P[j,i,A] = true

应按以下方式解释。假设 P[j, k, B] 为真。这意味着由从位置 j 开始的 k 个字符组成的字符串可以从非终结符 R B派生。如果 P[j + k, i - k, C] 也是如此，则从位置 j + k 开始的 i - k 个字符形成的字符串可以从非终结符 R C导出。因此，由于 R A → R B R C是一个产生式，因此从位置 j 开始的 i 个字符组成的字符串可以从 R A导出。

我认为将伪代码解释为

对于每个产生式 R A → R B R C：

如果 P[j,k,B] == true 且 P[j+k,ik,C] == true，则设置 P[j,i,A] = true

希望这可以帮助！

于 2013-04-15T01:10:01.260 回答