文脈自由文法変換

Question

Chomsky normal formをBackus–Naur Formに変換するソフトウェアがあれば教えてください。

Answer 1

私が指摘したように、BNFがすでにCNFに入っている私の元々の答えは間違っていました。 here（PDF）の説明どおり、文脈自由文法をCNFに変換することができます。変換プロセスは、Sipser第2版にも示されています。アクセス権がある場合は106-109ページを参照してください。私は、このプロセスを自動化する既存のソフトウェアがあるかどうかはわかりません（しかし、簡単に書けるように思えます）。

Answer 2

まあ、チョムスキーノーマルフォームとバッカス - ナウアフォームは、まったく同じ種類のコンセプトではないので、私は本当にそうは思わない。しかし、あなたがこのソフトウェアを必要としていることを教えてくれたら、私たちは手伝ってくれるかもしれません。

あなたが尋ねたところから、私はあなたがChomsky Normal FormにBNF文法を正規化するためのある種のコードを必要としていると仮定しています。私が知る限り、そのようなソフトウェアは存在しませんが、計算上実現可能なタスクであると仮定して、存在する可能性があります。

しかし、実際に必要なことについてさらに具体的に説明できる場合は、そのタスクに関する有用なアドバイスを提供することができます。

EDIT：私の本で少し掘り下げた後、任意のCFGをChomsky Normal Formに変換するアルゴリズムを定式化することが可能であることが判明しました。私は実際のアルゴリズムやその複雑さを持っていません。

Answer 3

JFLAPあなたが探していることをやるでしょう。

私はまだそれを使っていませんが、私のオートマタの教授が私に勧めました。

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