5

CYK アルゴリズムについて読んでいましたが、理解できない疑似コードの一部があります。疑似コード全体は次のとおりです。

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

誰かがこれらの疑似コードについてヒントをくれますか?

4

1 に答える 1

3

疑似コード

各プロダクション R A → R B R C :

P[j,k,B] および P[j+k,ik,C] の場合、P[j,i,A] = true を設定します

次のように解釈する必要があります。P[j, k, B] が true であるとします。つまり、位置 j から始まる k 個の文字から構成される文字列は、非終端記号 R Bから派生できます。P[j + k, i - k, C] が true である場合、位置 j + k から始まる i - k 文字から形成される文字列は、非終端 R Cから導出できます。したがって、R A → R B R Cは生成なので、位置 j から始まる i 文字から形成される文字列は、 R Aから派生できる場合です。

その疑似コードを次のように解釈すると役立つと思います

各プロダクション R A → R B R C :

P[j,k,B] == true かつ P[j+k,ik,C] == true の場合、P[j,i,A] = true と設定する

お役に立てれば！

于 2013-04-15T01:10:01.260 に答える