コンテキストフリー言語を変換するプログラムは、オートマトンを押し下げますか？

Question

コンテキストフリー言語をプッシュダウンオートマトンに変換するために、オンラインでアプレットやプログラムをオンラインで見つけることができません...どんな助けも大歓迎です。

Answer 1

手作業でできるのはとても簡単です。 PDAには、開始状態と最終状態Fがあり、2つの状態が唯一の状態です。移行（（s、空、空）、（f、s））を作成します。ここで、SはCFGの開始記号です。各ルールx - > yについて、xは非端子記号であり、yは端末と非末端の空の文字列である可能性があり、遷移（（f、empty、x）、（f、y））を行います。最後に、各端子記号aについて、ルール（（f、a、a）、（f、空））を追加します。

これが行うことは、スタックにスタート記号を押すことから始めることです。次に、スタックの上部にある非ターミナルを生産ルールの右側に置き換え、スタックの上部に端末文字を一致させてポップします。

Answer 2

でコードをチェックアウトしてください： https://github.com/p-raj/automataplus. 。 CFGをPDAに変換するだけでなく、他の同様のタスクにもコードが含まれています。

Answer 3

このソフトを試してみてください： https://github.com/navrkald/RegualConvertor。変換CFGのアルゴリズム全体をPDAにスローすることができます。 QTを使用してC ++で書かれ、セクションリリースでは、Windows用の自己実行可能なバイナリをすでに構築しています。