問題タブ [chomsky-normal-form]

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

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

私は次のことを証明しようとしています：

G がチョムスキー正規形の文脈自由文法である場合、w が長さ n ≥ 1 の L(G) に属する任意の文字列について、w の導出を行うには正確に 2n-1 ステップが必要です。

これを証明するにはどうすればよいでしょうか？

できるだけ早くあなたの助けが必要です。チョムスキー標準形に変換する必要があります。

いくつか試してみましたが、110Y などの混合パーツがあるため、いつも行き詰まります...

目標は、疑似コードを実際に動作するコードに変換することです。ほぼ解決したと思っていたのですが、何かがおかしいのです。

私が使っているルールは

擬似コードは次のとおりです。

実際のコードは次のとおりです。

私は得る：

しかし、おわかりのように、baba はその文法から派生する可能性があります。

この古い試験問題では、文法を CNF に変換する必要がありますが、提供された解決策が間違っていると思われます。

文法：

最初のステップでは、4 つの端末の変数を設定します。

2 番目のステップでは、端子を変数に置き換えます (現時点では S のプロダクションのみ):

3 番目のステップで、VAB の AB を次のように置き換えU -> ABます。

ソリューションでは、S プロダクションの AbB と bB (AXB と XB に設定) で何が起こっているのかわかりません。これは、S プロダクションに対して提供された回答です。

AbB が UX に設定され、bB が BX に設定されているのはなぜですか? 少なくとも bB を XB に設定するべきではありませんか?

最終的には、次の CFG をチョムスキー標準形に変換したいと考えています。

ただし、派生を正しく行っているかどうかはわかりません-ここに私が持っているものがあります:

非端末を端末に置き換える

これが正しい/正しい軌道に乗っているかどうか誰かに教えてもらえますか?

ありがとうございました。