加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Java > 正文

java – 无法理解CYK算法的伪代码

发布时间:2020-12-14 19:35:38 所属栏目:Java 来源:网络整理
导读:我正在阅读关于 CYK algorithm的内容,并且有一部分我无法理解的伪代码.整个伪代码是: 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
我正在阅读关于 CYK algorithm的内容,并且有一部分我无法理解的伪代码.整个伪代码是:
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,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,A] = true

有人会给出一些关于这些伪代码的提示吗?

解决方法

伪代码

For each production RA → RB RC:

if P[j,A] = true

应该用以下方式解释.假设P [j,B]为真.这意味着从位置j开始的k个字符形成的字符串可以从非终结RB导出.如果P [j k,i – k,C]也为真,那么从位置j k开始的i-k个字符形成的字符串可以从非终结RC导出.因此,由于RA→RB RC是生产,因此从位置j开始的i个字符形成的字符串可以从RA导出.

我认为这可能有助于将伪代码解释为

For each production RA → RB RC:

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

希望这可以帮助!

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读