非確定的プッシュダウンオートマトンのシミュレータ

Question

まあ、私は、非決定論的プッシュダウンオートマトン用にシミュレータを作成する必要があります。 すべてがokeyです、私は再帰やそれに類することをする必要があることを知っています。しかし、オートマトンをシミュレートする機能をどのように作成するのか分かりません。

私は制御の下にあるすべてのものを自動化ジェネレーター、スタック... 私はJavaでそれをやっているので、これは人がぶつかることができます。 誰かが似たようなことをしていれば、アドバイスを使うことができます。もちろん、別のスタックの問題、およびすべてのブランチの入力

Classes: class transit: 
    list<transit> -contains non deterministic transitions 
    state 
    input sign 
    stack sign class generator 
    it generate automaton from file clas NPA 
    public boolean start() - this function I am having trouble with 

：

これは、コードの私の現在の組織です。

オブジェクトNPAのコレクションで解決しようとしましたが、すべてのオブジェクトを開始しようとしましたが、機能しません。

Answer 1

さて、オートマトンの定義について考えてみましょう。状態と状態遷移機能があります。あなたはスタックを持っています。人生を刺激するのは、非決定論です。

しかし、すべての非決定論的有限オートマトンは同等の確定的FSAを持つという定理（ルックアップ）です。

対応するDFAを作成することができます。しかし、それは最悪のケースで指数関数的な空間です.DFA内のすべての状態は、NFA状態のパワーセットのサブセットに対応しています。

だから、代わりに "オンライン"を試すことができます。現在、同等のDFAを構築する代わりに、NFAをシミュレートします。状態遷移時には、到達する次の状態をすべて構築して、それらをいくつかのデータ構造に配置します。次に戻って、そのような各状態について次に何が起こるかを見てください。

Answer 2

JFLAPはオープ​​ンソースであり、これを（さらには！）チェックアウトしてみませんか？