Не может понять псевдокод алгоритма CYK

Question

Я читал об алгоритме 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

Кто-нибудь даст какие-нибудь подсказки об этом псевдокоде?

Answer 1

Псевдокод

Для каждой продукции R_A → R_B R_C:

если P[j,k,B] и P[j+k,ik,C], тогда установить P[j,i,A] = true

Следует интерпретировать следующим образом. Предположим, что это тот случай, когда P[j,k,B] верно. Это означает, что строка, образованная из k символов, начиная с позиции j, может быть получена из нетерминала R_B. Если это также случай, когда P[j+k,i-k,C] истинно, то строка, образованная из символов i - k, начинающихся в позиции j + k, может быть получена из нетерминального R_C. Следовательно, поскольку R_A → R_B R_C является продукцией, это тот случай, когда строка, образованная из символов i, начинающихся в позиции j, может быть получена из R_A.

Я думаю, что это может помочь интерпретировать этот псевдокод как

Для каждой продукции R_A → R_B R_C:

если P[j,k,B] == true и P[j+k,ik,C] == true, тогда установить P[j,i,A] = true

Надеюсь это поможет!