Geek asks and answers

Unable to understand pseudo-code CYK Algorithm

I read about the CYK algorithm , and there is one piece of pseudocode that I cannot understand. All pseudo code:

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

These parts confuse me:

    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

Will anyone give any hints of these pseudo codes?

+5
source share
1 answer

Pseudo code

For each product R A → R B R C:

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

It should be interpreted as follows. Assume that this is true that P [j, k, B] is true. This means that a string formed of k characters starting from position j can be obtained from the nonterminal R B. , P [j + k, - k, C] , , - 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, i-k, C] == true, P [j, i, A] = true

, !

+3

More articles:


All Articles