pushdown-automaton - JFLAP を使用してプッシュダウン オートマトンを実行する方法

Question

次の言語を認識する JFLAP を使用してプッシュダウン オートマトンを作成する必要があります。

そのためにはどのような手順を踏む必要がありますか? そして、それはどのように機能しますか？

Answer 1

この質問はcs.stackexchange.comに適していると思いますが、とにかくソリューションを追加します。

例の形成

実際には見た目よりも簡単です。例として、オカレンスに次の値があると考えてみましょう。

n = 2
m = 3
p = 1

これにより、次の文字列を形成できるはずです。

a ² b ³ c ¹ a ¹⁺³ b ² = aabbbcaaaabb

論理的理解の形成

これから、追跡する必要があるシンボルを決定する必要があります。

1. 外側のシンボルがn何度も発生することがわかっているため、ここをn,m ≥ 1追跡する必要があり、少なくとも1 回は発生する必要があります。n
2. 少なくともq = p+mとmが発生することはわかっているので、 の発生を追跡する必要があります。m
3. q = p+mの発生も保持する必要がある場合は、 と記載されているため、発生することもできないpことに注意してください。pp ≥ 0

正式な定義の形成

PDA Pを次の PDA にします。

P = (Q, Σ, Γ, τ, q ₀ , Z, q ₆ )

どこ：

• Q は、d-PDA の状態のセットです。
• Σ は、文字列を含む入力記号です。
• Γ は、集合 Γ = {a,b} を含むスタック シンボルです。
• q ₀は初期 (開始) 状態です
• Z はスタック シンボルです#
• q ₆は最終 (終了) 状態です

プッシュダウン オートマトンの作成

したがって、これから (JFLAP で) 次のオートマトンを作成できます。

ここでは、上記のようにシンボルを追跡しているだけですが、ここで注意すべき重要なことはq3、トランジションが 0 以上のトランジションでcあるということです。

また、シンボル#をスタック シンボルとして使用します。

シミュレーション

上記の入力 ( aabbbcaaaabb) でこの PDA をシミュレートすると、次の結果が得られます。