問題タブ [chomsky-normal-form]

チョムスキー標準形をバッカス・ナウア形に、またはその逆に変換するソフトウェアがあるかどうか誰か教えてもらえますか?

次の CFG を CNF の CFG に変換する必要があるという問題があります。

手順は次のとおりです。

1. イプシロン遷移を削除 - 完了
2. ユニットプロダクションを削除
3. 次の方法で CNF に変換します。
   1. 学期ごとに新しい非端末を導入する
   2. 生産ルールの端末を新しい非端末に置き換えます
   3. 各プロダクションの右側の長さを減らすために新しい非終端記号を導入する

上記の問題でそれを行う方法について少し混乱しています。ほとんどの場合、ステップ 2 とユニット プロダクションで混乱しています。

文法をチョムスキー標準形に翻訳する練習をしようとしています。私は通常の状況でこれを行う方法を理解していますが、今回は私が使用している文法は正しい再帰的です。（技術的には、文法は前の質問に対する答えなので、ガンマが間違っている可能性があります。）

εルールの代わりに固定シーケンスのルールを使用することでこれを実行できると思いますが、間違った方向に向かっていないことを確認したいと思います。例を使って説明する方が簡単です。

nが0より大きく3の倍数であるn'aを生成する文法の場合:(心配しないでください。これは私の実際の文法とはまったく異なります）

正しい翻訳は次のようになりますか？

すべての単語の言語Lの文脈自由文法（CFG）を見つけて、単語の各終端が、おそらく大きなアルファベットで偶数回出現するようにしますΣ

私の長いアプローチは（唯一の非終端記号はSです）：

これは正しいです？プロダクションは正しい単語を生成しますが、すべての単語を生成しますか？

編集：大きなアルファベットのCFGは、各端末が偶数回表示される言語を記述できますか？

EDIT_2：解が存在する場合、チョムスキー標準形が|Σ|で多項式になる可能性はありますか？？

文法をチョムスキー標準形(CNF)に変更したいです。

これは例です

私はこれを解決しようとします

答えはわかりません。それが正しいか間違っているか誰か教えてもらえますか？

なぜ文法をチョムスキー標準形に変換するのですか? 利点はありますか？

あなたの助けが必要です。私はこれらの作品を持っています：

チョムスキー正規形 (CNF) を適用する必要があります。

上記のルールを適用するには、次のことを行う必要があります。

1. ε 生成を消去する
2. ユニタリプロダクションを排除する
3. 不要な記号を削除

すぐに行き詰まります。その理由は、A がヌル可能シンボルであるためです (ε はその本体の一部です)。

もちろん、A 記号を削除することはできません。

誰かが最終的な解決策を得るのを手伝ってくれますか?

私はこれらの作品を持っています：

チョムスキー標準形を適用する必要があります

私の推論：

1) eps ルールを削除します。

私は得る：

2) 単位規則をなくす

ありません

3) 無駄な記号を削除する

私は得る：

したがって、CNF (Chomsky Normal Form) を適用した後の与えられた文法は次のようになります。

私は正しいですか？

以下の文法をチョムスキー標準形に変換します。すべての中間ステップを実行します。

さて、私が最初にしたことは、新しい開始変数を追加することでしたS0

だから今私は持っています

次に、すべてのラムダルールを削除しました。

次に、存在しないルールをチェックしS->Sて入力しました。A->Bそしてそれが私が思いついた答えでした、私はさらに何かをする必要がありますか、それとも私は何か間違ったことをしましたか？

私はCFGを使用していますが、特定の言語でルールを作成するたびに、CFGは嫌になります。それは1行になります：

チョムスキー標準形にすると正しい形になり、きれいになりますが、見た目をすっきりさせるためのアイデアはないかと思いました。

つまり、lang：

私のCFG（グロス）：

誰かが私の悪い習慣を手伝ってくれますか？