pushdown-automaton - プッシュダウン オートマトン (PDA)

Question

a^2n b^n, n>0 を受け入れる pda プッシュダウン オートマトンを作成しようとしていますが、最後の部分が正しいかどうかはわかりません

(p0, a, z0) = (p0, az0)
(p0, a, a) = (p0, aa)
(p0, b, a) = (p1, λ)
(p1, λ, b) = (p2, λ)   <=
(p2, 0, b) = (p1, λ)  <=
(p2, λ, z0) = (p3, λ)  <=

Answer 1

あなたの答えに関する限り、最初の 2 つのステップでは、1 つのステップだけで a を押しています。現在の設計では、マシンは a^2nb^n の形式ではない aaabb を受け入れます。ですから、別々に 2 つの状態に分けたほうがよいでしょう。私によると、正しい答えは次のようなものかもしれません：

1. (p0, a, z0) = (p0, az0)
2. (p0、a、a) = (p1、aa)
3. (p1、a、a) = (p0、aa)
4. (p1、b、a) = (p2、λ)