normalization - 文脈自由文法変換

Question

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

Answer 1

ええと、チョムスキー標準形とバッカス・ナウア形は実際には同じ種類の概念ではないので、私は実際にはそうは思いません。しかし、あなたがこのソフトウェアを必要としているものを私たちに話してくれれば、私たちが助けることができるかもしれません。

さて、あなたの質問から、BNF文法をチョムスキー標準形に正規化するためのある種のコードが必要だと思います。私の知る限り、そのようなソフトウェアは存在しませんが、実際に計算上実行可能なタスクであると仮定すると、いくつか存在する可能性があります。

ただし、実際に必要なものについてより具体的にすることができれば、そのタスクについて役立つアドバイスを提供することができます。

編集：私の本を少し掘り下げた後、任意のCFGをチョムスキー標準形に変換するアルゴリズムを定式化することは非常に可能であることがわかりました。しかし、実際のアルゴリズムやその複雑さはありません。

Answer 2

たぶん、JFLAPはあなたが探しているものを実行します。

私自身はまだ使用していませんが、Automata の教授から勧められました。

「JFLAPとは？」をみる ページ、あなたが探しているもののように聞こえる「CFG -> CNF」から変換できるようです。

Answer 3

指摘されたように、BNFはすでにCNFにあるという私の最初の答えは間違っていました。ここで説明されているように、文脈自由文法をCNFに変換できます（PDF）。変換プロセスは、Sipser2ndEdにも示されています。アクセスできる場合は、106〜109ページ。このプロセスを自動化する既存のソフトウェアがあるかどうかはわかりません（ただし、作成するのは簡単に思えます）。