Không thể hiểu mã giả CYK Algorithm

Question

Tôi đã đọc về số CYK algorithm và có một phần của mã giả tôi không thể hiểu được. Toàn bộ giả là:

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 

Những bộ phận được mà tôi đang bối rối:

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 

một người nào đó sẽ đưa ra một số gợi ý về những giả?

Answer 1

Các giả

Đối với mỗi R sản xuất _Một → R _B R _C:

nếu P [j, k, B] và P [j + k, ik , C] rồi đặt P [j, i, A] = true

Cần được diễn giải theo cách sau. Giả sử rằng đó là trường hợp P [j, k, B] là đúng. Điều đó có nghĩa là chuỗi được tạo thành từ các ký tự k bắt đầu từ vị trí j có thể bắt nguồn từ không có R _B. Nếu đó cũng là trường hợp P [j + k, i - k, C] là đúng, thì chuỗi được hình thành từ các ký tự i - k bắt đầu từ vị trí j + k có thể được lấy từ không có chữ R _C. Do đó, kể từ R _Một → R _B R _C là một sản xuất, đó là trường hợp đó các chuỗi hình thành từ các nhân vật tôi bắt đầu ở vị trí j có thể được bắt nguồn từ R _Một.

tôi nghĩ rằng nó có thể giúp giải thích rằng giả như

Đối với mỗi R sản xuất _Một → R _B R _C:

nếu P [j, k, B] == true và P [j + k, ik, C] == true, sau đó thiết lập P [j, i, A] = true

Hope this helps!