无法理解CYK算法伪code

本文介绍了无法理解CYK算法伪code的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我在阅​​读有关 CYK算法，且有假$ C一部分$ C我无法理解。整个伪code是：

I was reading about the CYK algorithm, and there is one part of pseudo-code I cannot understand. The whole pseudo-code is:

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

会有人给出一些提示有关这些伪code？

Would someone give some hints about these pseudocode?

推荐答案

伪code

对于每个生产 - [R A ＆RARR; - [R B 研究 C ：

For each production RA → RB RC:

如果P [J，K，B]和P [J + K，IK，C]，然后设置P [J，I，A] =真

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

应PTED以如下方式除$ P $。假设它的那个P [J，K，B]为真时。这意味着，从起始位置jķ字符组成的字符串可以来源于非终结 - [R B 。如果它也是P [J + K，I - K，C]的情况是真实的，然后从我形成的字符串 - K起始位置j + K字可以从非终结 - [R C 。因此，由于R A ＆RARR; - [R B 研究 C 是一家集生产，这是从开始位置j第i个字符组成的字符串，可以从研发导出的情况下A

Should be interpreted in the following way. Suppose that it's the case that P[j, k, B] is true. That means that the string formed from k characters starting at position j can derived from the nonterminal RB. If it's also the case that P[j + k, i - k, C] is true, then the string formed from the i - k characters starting at position j + k can be derived from nonterminal RC. Therefore, since RA → RB RC is a production, it's the case that the string formed from the i characters starting at position j can be derived from RA.

我想这可能有助于跨preT的伪code为

I think it might help to interpret that pseudocode as

对于每个生产 - [R A ＆RARR; - [R B 研究 C ：

For each production RA → RB RC:

如果P [J，K，B] ==真和P [J + K，IK，C] == true，则设置P [J，I，A] =真

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

希望这有助于！