5

文字列が文脈自由文法の一部であるかどうかを検証するにはどうすればよいですか? 仮想だけでなく、そのためのアルゴリズムを構築しますか?

次のような規則を持つ文脈自由文法が与えられた場合、

  • V-> v1v2
  • v1->1 | 1v1
  • v2-> 2 | 2対2

これが言語 1^n 2^n であることは明らかです。しかし、実際にそうであるかどうかを検証するアルゴリズムをどのように使用しますか。私はJavaでこれを達成しようとしています。

4

1 に答える 1

7

文字列が文脈自由文法によって生成されるかどうかを判断するための 2 つのアルゴリズムであるEarley のアルゴリズムまたはCYK アルゴリズムを調べることをお勧めします。Earley のアルゴリズムは、文法の生成規則に関係なく、長さ n の任意の文字列に対して時間 O(n 3 ) で実行されます (ただし、big-O 表記の定数項は文法に依存します)。一方、CYK アルゴリズムでは、最初に文法が必要です。O(n 3 ) ランタイムを保証するためにチョムスキー標準形に変換されます。

お役に立てれば！

于 2013-03-24T00:03:57.813 に答える