2

CYK 構文解析アルゴリズムを学習しようとしています。

この一連の文法規則について、結果として得られる表は、与えられた 2 つの文に対して正しいでしょうか?

S -> NP VP
VP -> VB NP
NP -> DT NN
PP -> IN NP
NP -> NP PP
NP -> NN
VP -> VP PP
IN -> with
NN -> dog
NN -> cat
VB -> ate
NN -> mouse
DT -> the


['S']
[None, None]
[None, None, 'VP']
['NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog']


['S']
['NP', None]
['NP', None, 'VP']
['NP', None, None, 'NP']
[None, None, 'VP', None, None]
[None, None, 'VP', None, None, 'PP']
['NP', None, None, 'NP', None, None, 'NP']
['DT', 'NN', 'VB', 'DT', 'NN', 'IN', 'DT', 'NN']
['the', 'cat', 'ate', 'the', 'dog', 'with', 'the', 'cat']
4

2 に答える 2

1

不必要なルールがいくつかあるため、最初に文法を最小限に抑えることができますnot in CNF。

もっと簡潔に見ると、たまたまNone最初の例、2 行目、2 列目にあります。実際には を持つことは可能ですがS、CYK のロジックは などのさらなる最適化を行うことができないためですNP->NN。そこからS -> NP VP、前述のNoneセルが欠落します。CYK はこれらを実行できないため、文法は CNF でなければなりません。したがって、基本的には、C++ プログラム (C++ ライブラリなし) に C コンパイラを適用しようとしているようなものです。そして、トップで正しい結果を得ることができたのは幸運でした。

そうは言っても、私はあなたの2番目の例にふけるつもりはありません.

明確にするために、次の 2 つの形式のみCNFの規則がある場合、文法は有効です。

S -> AB
A -> A

明らかに、そのようなものNP -> NNはCNFにはありません。

于 2016-07-18T10:19:00.347 に答える