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

a^2nb^n n>=0 的确定性下推自动机
绕过替代 a 并推动其余 a

Answer 2

就您的答案而言，在您的前两个步骤中，您只需一步推动 a。使用当前设计，机器将接受 aaabb，它不是 a^2nb^n 的形式。所以最好把它分别分成两个状态。在我看来，正确的答案可能是这样的：

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

Answer 3

q0是初始状态，qf最终是状态；^为空：

Q(q0,a,z)=Q(q1,z)
Q(q0,a,a)=Q(q1,aa)
Q(q0,b,a)=Q(q0,^)
Q(q0,^,z)=Q(qf,z)
Q(q1,a,z)=Q(q2,az)
Q(q1,a,a)=Q(q2,a,a)
Q(q2,a,a)=Q(q0,az)