CYKアルゴリズムの擬似コードを理解できません

Question

私はCYK algorithmについて読んでいましたが、理解できない擬似コードの部分があります。全体の擬似コードは次のとおりです。

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 

誰かがこれらの擬似コードについていくつかのヒントを与えるだろうか？

Answer 1

擬似各生産R _について

→ 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 _ため → R _B R _Cは、位置jから始まるI文字から形成された文字列がR に由来することができるケースの製造です。

は、私はそれが各生産R _について

としてその擬似コードを解釈するのに役立つかもしれないと思う → R _B R _C：

もしP [J、K、B] = trueとP [j + k、ik、C] == trueの場合、P [j、i、A] = trueを設定する。

これは役に立ちます。