PDAをDFAに変換する

Question

私はPDAをDFAに変換しようとしています。 PDAのスタックにはn個以上のシンボルが決して含まれません。

ご協力いただければ幸いです。スタック上のシンボルのを押して各遷移についてあなたが次のポップ遷移に部分グラフをコピーする必要があります。

は、私は完全なソリューションが、ただのアイデアを持っていないあなたに

Answer 1

ありがとうございます。新しいサブグラフは、ののPDAの対応するサブグラフと同じ部分文字列を受け入れる必要があります。このようなトランジションを検索するときは、内部グラフからインサイドプッシュとポップがないように内側から移動する必要があります。したがって、最初の置換は2つの変換からなり、後続の部分グラフは大きくなります。