'Pushdown Automata (PDA)

I'm trying to write a pda pushdown automata that accept a^2n b^n, n>0 but I'm not sure if the last part is correct

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


Solution 1:[1]

As far as your answer is concerned, in your first two steps you are pushing a's in only one step. With the current design the machine would accept aaabb which is not in the form a^2nb^n. So it's better to divide it in two states separately. According to me the right answer might be something like:

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

Solution 2:[2]

Deterministic push down automata for a^2nb^n n>=0
Bypass altetnate a's and push rest of a's

flipchart capture

Solution 3:[3]

q0 is initial state and qf is final is state; ^ is for null:

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)

Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source
Solution 1 Omkar Pathak
Solution 2 user1859022
Solution 3 Adrian Mole

Related Questions