无法理解CYK算法伪code [英] Cannot understand CYK Algorithm pseudo-code

问题描述

我在阅​​读有关 CYK算法，且有假$ C一部分$ C我无法理解。整个伪code是：

I was reading about the CYK algorithm, and there is one part of pseudo-code I cannot understand. The whole pseudo-code is:

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

会有人给出一些提示有关这些伪code？

Would someone give some hints about these pseudocode?

推荐答案

伪code

对于每个生产 - [R <子> A ＆RARR; - [R <子> B 研究<子> C ：

For each production R_A → R_B R_C:

如果P [J，K，B]和P [J + K，IK，C]，然后设置P [J，I，A] =真

if P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true

应PTED以如下方式除$ P $。假设它的那个P [J，K，B]为真时。这意味着，从起始位置jķ字符组成的字符串可以来源于非终结 - [R <子> B 。如果它也是P [J + K，I - K，C]的情况是真实的，然后从我形成的字符串 - K起始位置j + K字可以从非终结 - [R <子> C 。因此，由于R <子> A ＆RARR; - [R <子> B 研究<子> C 是一家集生产，这是从开始位置j第i个字符组成的字符串，可以从研发<子>导出的情况下A <子/>

Should be interpreted in the following way. Suppose that it's the case that P[j, k, B] is true. That means that the string formed from k characters starting at position j can derived from the nonterminal R_B. If it's also the case that P[j + k, i - k, C] is true, then the string formed from the i - k characters starting at position j + k can be derived from nonterminal R_C. Therefore, since R_A → R_B R_C is a production, it's the case that the string formed from the i characters starting at position j can be derived from R_A.

我想这可能有助于跨preT的伪code为

I think it might help to interpret that pseudocode as

对于每个生产 - [R <子> A ＆RARR; - [R <子> B 研究<子> C ：

For each production R_A → R_B R_C:

如果P [J，K，B] ==真和P [J + K，IK，C] == true，则设置P [J，I，A] =真

if P[j,k,B] == true and P[j+k,i-k,C] == true, then set P[j,i,A] = true

希望这有助于！

这篇关于无法理解CYK算法伪code的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！