コンテキストフリー言語をオートマトンをプッシュダウンするプログラム？

Question

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

Answer 1

手で行うのはとても簡単です。 PDAは、開始状態sおよび最終状態fを有し、唯2つの状態のみを有する。トランジション（（s、空、空）、（f、S））を作成します。ここで、SはCFGの開始シンボルです。 Xが非終端記号であり、Yが端末と非終端記号の空文字列である各規則X-> Yに対して、（（f、empty、X）、（f、Y））を遷移させます。最後に、各端末シンボルaに対して、ルール（（f、a、a）、（f、empty））を追加します。

これは、スタック上の開始記号を押すことから始まります。次に、スタックの最上部にある非終端記号を、その生成規則の右端に置き換え、スタックの先頭にあるすべての終端文字にマッチしてポップします。

Answer 2

コードをご確認ください：https://github.com/P-Raj/AutomataPlus。それは、CFGをPDAに変換するだけでなく、他の同様のタスクのためのコードを含んでいます。

Answer 3

このソフトを試してください：https://github.com/navrkald/regularConvertor 変換CFGの全アルゴリズムをPDAにスローすることができます。 Qtを使用してC++で書かれており、セクションリリースでは、すでにWindows用のバイナリを自作してビルドしています。