3

そのため、ウィキペディアや多くのパワーポイント/pdfでCYKアルゴリズムについて読んでいます。

ウィキペディアには、私が言おうとしていることを 100% 理解していない部分があります。分解してくれませんか？

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

私を本当に混乱させる部分は、「P[1、n、x]のいずれかが真である場合（xはセットsに対して反復され、sはRsのすべてのインデックスです）、Sは言語のメンバーです。そうでない場合、Sはメンバーではありません言語の」

存在する n と x が true の場合、それはメンバーであると言っていますか? それとも、文字列の長さ n と x が true の場合、それはメンバーですか? または完全に異なる何か？

また、Xとは正確には何ですか？

編集：

みんなありがとう、私は間違いなくそれを行う方法を学びました。両方の回答を選択した回答として取得できれば幸いです。

4

2 に答える 2

3

CYK アルゴリズムを実行しているときは、基本的に、下三角行列をその下から最上部の要素まで埋めています。が列インデックス、が行インデックス、が非終端記号である要素(j,i,x)がtrue の場合は常に、記号 から単語のサブシーケンスtoを生成できることを意味します。jixjj+i-1Rx

あなたの目標は、開始記号の 1 つから単語全体を生成することです。単語全体を生成する可能性に対応する(1,n,x)要素は、マトリックスの左端と最上部の要素です。ここで、xは非終端記号のインデックスです。開始記号の 1 つで開始する必要があるため、すべての非終端記号のサブセット ( のサブセット) だけを探していますs。開始記号の 1 つから単語全体を生成できた場合は、その単語が言語の一部であると述べるだけです。そのような開始記号が存在しない場合、その単語を生成することはできず、その単語は文法で記述された言語の一部ではありません。

于 2013-02-05T10:09:46.360 に答える
1

つまり、P[1,n,x] が任意の開始非終端 x に対して true の場合、非終端 x として文字列全体 (1 から n までの語彙トークン) が解析されるということです。このアルゴリズムでは、P[a,b,c] = true は、インデックス a で始まり、長さ b を持つ字句トークンの部分文字列が、非終端 c として解析できることを意味します。

于 2013-02-05T10:03:42.867 に答える