私は次のことを証明しようとしています：
G がチョムスキー正規形の文脈自由文法である場合、w が長さ n ≥ 1 の L(G) に属する任意の文字列について、w の導出を行うには正確に 2n-1 ステップが必要です。
これを証明するにはどうすればよいでしょうか？
質問する
10151 次
1 に答える
16
ヒントとして - チョムスキー標準形のすべてのプロダクションはいずれかの形式を持っているため
S → AB、非終端記号 A および B の場合、または次の形式
S → x、端末 x の場合、
次に、文字列の導出は次のように機能します。
- ちょうど n 個の非終端記号の文字列を作成し、次に
- 各非ターミナルを単一のターミナルに展開します。
最初の形式の生成を適用すると、非終端記号の数が k から k + 1 に増えます。これは、1 つの非終端記号 (-1) を 2 つの非終端記号 (+2) に置き換えると、+1 非終端記号の正味ゲインが得られるためです。1 つの非終端記号から始めたので、最初の形式を n - 1 回生成する必要があります。次に、非終端記号を終端記号に変換するために、2 番目の形式をさらに n 個必要とし、合計で n + (n - 1) = 2n - 1 個の生成を行います。
まさにこれだけの数が必要であることを示すために、矛盾による証明を行い、これ以上またはそれ以下ではできないことを示すことをお勧めします。ヒントとして、作成された各タイプのプロダクションの数を数えてみて、それが 2n - 1 でない場合は、文字列が短すぎるか、まだ非終端記号が残っていることを示してください。
お役に立てれば！
于 2013-03-03T19:13:11.510 に答える