Nie rozumiem pseudokodu algorytmu CYK

Question

Czytałem o CYK algorithm i jest jedna część pseudokodu, którego nie rozumiem. Cały pseudokod jest:

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 

Te części są który ja mylić:

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 

Czy ktoś podać kilka wskazówek na temat tych Pseudokod?

Answer 1

pseudokod

Dla każdego produkcji R → R _B R _C:

jeżeli P [j, k, B] i P [j + k ik , C] następnie ustawić P [j, i, A] = true

Należy interpretować w następujący sposób. Załóżmy, że to prawda, że ​​P [j, k, B] jest prawdziwe. Oznacza to, że ciąg utworzony z postaci k zaczynając od pozycji j może pochodzić od nieterminalnego R _B. Jeśli jest również prawdą, że P [j + k, i-k, C] jest prawdziwe, to łańcuch utworzony ze znaków i-k rozpoczynających się od pozycji j + k może pochodzić od nieterminalnego R _C. W związku z tym, jako R → R _B R _C jest produkcja, to jest tak, że łańcuch utworzony z postaci I, wychodząc z pozycji j może pochodzić z R .

myślę, że może to pomóc w interpretacji tego Pseudokod jako

Dla każdej produkcji R → R _B R _C:

jeśli P [j, k, B] == true i P [j + k, ik, C] == true, następnie ustaw P [j, i, A] = true

Mam nadzieję, że to pomoże!