Push Down Automata - Examples

 Example-1

1. The Language

$$L = \{ww^R : w \in \{a, b\}^+\}$$

• Example strings: aa, abba, baab, ababba, …

• Not in the language: ab, aabb, abb, …

• Basically, the string must be a palindrome of even length.

---

2. The Core Idea

• When reading the first half ($w$), we push symbols onto the stack.

• For the second half ($w^R$), we pop and compare: each input symbol must match the stack top.

• At the end, if everything matches and stack returns to $z$, accept.

---

3. The Difficulty

We don’t know where the middle of the string is.

• This is exactly where nondeterminism helps.

• The NPDA can guess the middle (i.e., when to stop pushing and start popping).

• Only the “correct guess” leads to acceptance.

---

4. The NPDA Definition

$$M = (Q, Σ, Γ, δ, q_0, z, F)$$

• $Q = \{q_0, q_1, q_2\}$
  

• $\Sigma = \{a, b\}$ (input symbols)

• $\Gamma = \{a, b, z\}$ (stack symbols)

• Start state = $q_0$, start stack symbol = $z$
  

• Final state set = $F = \{q_2\}$
  

---

5. Transition Function (informal)

1. In $q_0$: Pushing phase

   • Read a → push a.

   • Read b → push b.

   • ε-transition: nondeterministically switch from $q_0$ to $q_1$ (guess the middle).

2. In $q_1$: Popping & Matching phase

   • On input a with stack top a → pop.

   • On input b with stack top b → pop.

3. In $q_1$: End check

   • If stack has just z and input finished → ε-move to $q_2$.

4. In $q_2$: Accepting state

   • Input consumed, stack back to z.

---

6. Example Run: Input = abba

Let’s trace:

Initial: (q0, abba, z)

1. Read a, push: (q0, bba, az)

2. Read b, push: (q0, ba, baz)

3. Nondeterministic choice:

   • Option A: keep pushing (b on stack).

   • Option B: ε-move to $q_1$ (switch to popping).
     We choose B: (q1, ba, baz)

4. In $q_1$:

   • Read b, pop b: (q1, a, az)

   • Read a, pop a: (q1, ε, z)

5. Input finished, stack = z. ε-move → (q2, ε, z)

✅ Accepted.

---

7. Why Nondeterminism Is Needed

• If the PDA always kept pushing in $q_0$, it wouldn’t know the middle.

• If it switched too early, stack/input wouldn’t match.

• Only one of the nondeterministic branches leads to success.

Thus, palindromes (except odd-length) require nondeterminism, showing DPDA < NPDA.

---

✅ Summary:

• Finite automata cannot handle palindromes.

• Even DPDAs cannot — we really need nondeterminism here.

• This example beautifully illustrates the power of NPDA over DPDA

Example-2

Construct a PDA for

$$L=\{0^n1^m2^m3^n \mid n \ge 1,\; m \ge 1\},$$

Informal idea 

1. Read one or more 0’s and push a 0 for each onto the stack. (enforces $n\ge1$).

2. When the first 1 appears, switch to pushing 1’s (one or more, enforces $m\ge1$).

3. On the first 2, begin popping a 1 for every 2. If a 2 appears while the top of stack is 0 (i.e., more 2’s than 1’s so far), there is no transition → reject. After all 1’s are popped, the top will be 0.

4. When 2’s are finished, the next symbol must be 3. For each 3 pop one 0.

5. If input is finished and the stack has only the bottom marker, accept.

We will accept by reaching a final state (after an ε-move when stack is back to bottom marker).

Formal PDA

Let

$$M = (Q,\Sigma,\Gamma,\delta,q_0,z,F)$$

where

• $Q=\{q_0,q_1,q_2,q_3,q_f\}$
  

  • $q_0$: pushing 0’s (start)

  • $q_1$: pushing 1’s

  • $q_2$: popping 1’s while reading 2’s

  • $q_3$: popping 0’s while reading 3’s

  • $q_f$: accepting final state

• $\Sigma=\{0,1,2,3\}$ (input alphabet)

• $\Gamma=\{0,1,z\}$ (stack alphabet; z is bottom marker)

• Start state $q_0$, start stack symbol $z$
  

• $F=\{q_f\}$
  

We accept by final state; after popping all 0’s and returning to bottom marker z we take an ε-move to qf.

Transition function $\delta$

I list only moves that exist (any configuration not covered has no move → rejected). Notation:

$$\delta(q,\; a,\; X)\ni (p,\; \gamma)$$

means: in state $q$ reading input symbol $a$ with stack top $X$, go to state $p$ and replace $X$ by string $\gamma$ (where $\gamma\in\Gamma^*$). ε for input means an ε-move; ε as stack replacement means pop.

(1) Push 0’s in $q_0$

• $\delta (q_0,0,z)\ni (q_0,0z)\; —\; first\; 0\; (push\; 0\; above\; bottom).$

• $\delta(q_0,\,0,\,0)\ni (q_0,\,00)$ — push more 0’s.

(2) First 1 — move to $q_1$ and start pushing 1’s (this enforces at least one 1)

• $\delta(q_0,\,1,\,0)\ni (q_1,\,10)$— reading first 1 when top is 0; push 1 above that 0.
  (We do not allow reading 1 with top z — that would mean no 0’s before the 1 so such input is rejected, enforcing $n\ge1$.)

(3) Continue pushing 1’s in $q_1$

• $\delta (q_1,1,1)\ni (q_1,11)—\; push\; another\; 1.$

• $\delta (q_1,1,0)\ni (q_1,\mathrm{10)\; —\; push\; 1\; above\; a\; 0\; (possible\; if\; no\; 1s\; yet\; but\; still\; valid).}$

(4) First 2 — begin popping 1’s, move to $q_2$ (enforces at least one 2)

• $\delta(q_1,\,2,\,1)\ni (q_2,\,\varepsilon)$ — on first 2 pop one 1 and enter pop-1 phase.
  (There is no $\delta(q_1,2,0)$ — if a 2 appears while top is 0 at this stage, the machine has no move and the string is rejected. This prevents more 2’s than 1’s.)

(5) Continue popping 1’s in $q_2$

• $\delta(q_2,\,2,\,1)\ni (q_2,\,\varepsilon)$ — for each subsequent 2 pop one 1.

(6) After all 1’s popped, when top is 0, a 3 starts the popping-0 phase (move to $q_3$)

• $\delta(q_2,\,3,\,0)\ni (q_3,\,\varepsilon)$ — first 3 pops a 0 and moves to q3 (enforces at least one 3).

(There is no $\delta(q_2,2,0)$ — so extra 2’s when there are no 1’s left is rejected.)

(7) Continue popping 0’s in $q_3$

• $\delta(q_3,\,3,\,0)\ni (q_3,\,\varepsilon)$ — each 3 pops a 0.

(8) Accept when input finished and stack is back to bottom marker z

• $\delta(q_3,\,\varepsilon,\,z)\ni (q_f,\,z)$ — ε-move to accepting state (stack unchanged except bottom marker).
  (There is no transition on 0,1,2 in $q_3$ except the ones above; any unexpected symbol causes rejection.)

Example trace 

Take $n=2,m=2$ string: 00112233 (which is $0^2 1^2 2^2 3^2$).

Start: $(q_0,\;00112233,\;z)$

1. read 0: $(q_0,\;0112233,\;0z)$ — used $\delta(q_0,0,z)$
   

2. read 0: $(q_0,\;112233,\;00z)$ — used $\delta (q_0,0,0)$

3. read 1: $(q_1,12233,10z)\; —\; used$$\delta(q_0,1,0)$ (first 1)

4. read 1: $(q_1,\;2233,\;110z)$ — used $\delta(q_1,1,1)$
   

5. read 2: $(q_2,\;233,\;10z)$— used $\delta(q_1,2,1)$ (first 2, popped a 1)

6. read 2: $(q_2,\;33,\;0z)$ — used $\delta(q_2,2,1)$ (pop the final 1)

7. read 3: $(q_3,\;3,\;z)$ — used $\delta(q_2,3,0)$ (first 3, pop a 0)

8. read 3: $(q_3,\;\varepsilon,\;z)$ — used $\delta(q_3,3,0)$ (pop final 0)

9. input finished and stack top is z, take ε-move: $(q_f,\;\varepsilon,\;z)$ — accepted.

Input : 0 0 1 1 1 2 2 2 3 3 

Result : ACCEPTED 

Input : 0 0 0 1 1 2 2 2 3 3 

Result : NOT ACCEPTED

Example-3

 let’s construct a clear, lecture-ready PDA for

$$L=\{0^{n}1^{m}\mid n\ge 1,\; m\ge 1,\; m>n+2\},$$

Step-1: On receiving 0 push it onto stack. On receiving 1, ignore it and goto next state

Step-2: On receiving 1, ignore it and goto next state

Step-3: On receiving 1, pop a 0 from top of stack and go to next state

Step-4: On receiving 1, pop a 0 from top of stack. If stack is empty, on receiving 1 ignore it and goto next state

Step-5: On receiving 1 ignore it. If input is finished then goto last state . 

Formal PDA

Let

$$M=(Q,\Sigma,\Gamma,\delta,q_0,z,F)$$

where

• $Q=\{q_0,q_1,q_2,q_3,q_4,q_f\}$
  

• $\mathrm{\Sigma }=\{0,1\}$

• $\mathrm{\Gamma }=\{0,z\}\; with$$z$ the bottom marker

• start state $q_0$ start stack symbol $z$
  

• $F=\{q_f\}$

Acceptance by final state. (We leave z on the stack and move to $q_f$ by an ε-move when appropriate.)

Transition function (only defined moves)

Notation: $\delta(q,\; a,\; X)\ni (p,\; \gamma)$

(Phase 1) push zeros in $q_0$:

• $\delta(q_0,\,0,\,z)\ni (q_0,\,0z)$
  

• $\delta (q_0,0,0)\ni (q_0,00)$

(first 1 — ignore & go to $q_1$)

• $\delta (q_0,1,0)\ni (q_1,0)$ 

(second 1 — ignore & go to $q_2$)

• $\delta(q_1,\,1,\,0)\ni (q_2,\,0)$
  

(start popping zeros on next 1 — go to $q_3$)

• $\delta(q_2,\,1,\,0)\ni (q_3,\,\varepsilon)$ — pop one 0 and enter popping mode

(while popping zeros — stay in $q_3$)

• $\delta(q_3,\,1,\,0)\ni (q_3,\,\varepsilon)$ — pop one 0 per 1

(after all zeros are popped: the next 1 is the 3rd extra — go to $q_4$)

• $\delta(q_3,\,1,\,z)\ni (q_4,\,z)$ — when top is z and a 1 arrives, move to q4 (leave z)

(in accepting-phase $q_4$ allow more 1s)

• $\delta(q_4,\,1,\,z)\ni (q_4,\,z)$
  

(final ε-move to accepting state when input finished and stack has only z)

• $\delta (q_4,\epsilon ,z)\ni (q_f,z)$

All other combinations (input symbol & stack top) have no transition (that branch dies)

Example traces

1. Accepting example: $n=2,\; m=5$ — input 00 11111 (m-n=3 → should accept).

• Start: $(q_0,0011111,z)$

• Read 0: $(q_0,\,0\,11111,\,0z)$

• Read 0: $(q_0,11111,00z)$

• Read 1 (1st ignored): $(q_1,\,1111,\,00z)$
  

• Read 1 (2nd ignored): $(q_2,111,00z)$

• Read 1 (pop a 0): $(q_3,\,11,\,0z)$
  

• Read 1 (pop a 0): $(q_3,1,z)$

• Read 1 (top z → move to q4): $(q_4,\,\varepsilon,\,z)$
  

• Input finished, ε-move to qf → accepted.

2. Rejected example (not enough extras): $n=2,m=4$— 00 1111 (m-n=2): following the same trace stops in q3 with top z after consuming last 1 but never reached q4; input finishes in non-accepting state → rejected.

3. Rejected example (no zeros): input 1111 — q0 has no 1-transition when top is z, so no move from start → rejected (ensures $n\ge1$).

Example-4

Build a PDA for

$$L=\{a^n b^n \mid n \ge 1\},$$

 This PDA is deterministic: it pushes A for every a, then when the first b appears it switches to popping A for every b. We accept by final state when the input is exhausted and only the bottom marker remains.

Formal PDA

Let

$$M=(Q,\Sigma,\Gamma,\delta,q_0,z,F)$$

where

• $Q=\{q_0,q_1,q_f\}$
  

  • $q_0$: push phase (reading a's) — start state

  • $q_1$: pop phase (reading b's)

  • $q_f$: accepting final state

• $\Sigma=\{a,b\}$
  

• $\Gamma=\{A,z\}$ where z is the bottom-of-stack marker and A is the stack symbol pushed for each a.

• start state $q_0$ and start stack symbol $z$
  

• $F=\{q_f\}$
  

We accept by reaching $q_f$after consuming the whole input (stack may contain only z).

Transition function 

Notation: $\delta(q,\;x,\;X)\ni (p,\;\gamma)$meaning in state $q$ reading input symbol $x$ (or $x=\varepsilon$) with stack top $X$, go to state $p$ and replace $X$ by string $\gamma$(ε means pop).

Push A for each a (stay in $q_0$):

• $\delta(q_0,\,a,\,z)\ni (q_0,\,Az)$
  

• $\delta(q_0,\,a,\,A)\ni (q_0,\,AA)$
  

On first b, switch to pop-phase and pop one A:

• $\delta(q_0,\,b,\,A)\ni (q_1,\,\varepsilon)$
  

(There is intentionally no $\delta(q_0,b,z)$— that disallows strings that start with b or have no a — enforcing $n\ge \mathrm{1.)}$

While in pop-phase $q_1$, pop one A for each b:

• $\delta (q_1,b,A)\ni (q_1,\epsilon )$

When input finished and stack is just bottom marker, accept:

• $\delta (q_1,\epsilon ,z)\ni (q_f,z)$

(We leave z unchanged and move to final state. Alternatively you could accept by empty-stack by popping z with an ε-move; both are equivalent up to standard constructions.)

Example trace 

Take input a a b b:

Start: $(q_0,aabb,z)$

1. read a: $(q_0,abb,Az)\; via$$\delta(q_0,a,z)=(q_0,Az)$
   

2. read a: $(q_0,\;bb,\;AAz)$ via $\delta(q_0,a,A)=(q_0,AA)$
   

3. read b: $(q_1,\;b,\;Az)$via $\delta(q_0,b,A)=(q_1,\varepsilon)$ (first b, switch to pop-phase)

4. read b: $(q_1,\;\varepsilon,\;z)$ via $\delta(q_1,b,A)=(q_1,\varepsilon)$ (pop last A)

5. input finished and stack top is z: $(q_f,\;\varepsilon,\;z)$ via $\delta(q_1,\varepsilon,z)=(q_f,z)$ → accepted.

If the numbers of a and b differ, either a pop will be attempted when no A is present (no transition) or after finishing input some A remain (no ε-move to $q_f$), so the string is rejected.

Example-5

Build a PDA for

$$L=\{\,w c w^{R} \mid w\in\{0,1\}^*\,\},$$

(i.e. strings with a single center symbol c and a right half that is the reverse of the left half). The PDA will follow your steps:

• push every input symbol (0 or 1) until the c is seen;

• on reading c switch to the matching phase;

• thereafter, for each input symbol (0 or 1) pop the same symbol from the stack;

• accept iff the input is exhausted and only the bottom marker remains.

Informal description (phases)

• q0 (push phase) — start here. For each 0 or 1 read, push that symbol on the stack.

• On reading the central c, do not change the stack; move to q1.

• q1 (match/pop phase) — for each symbol 0 or 1 read, compare it with the stack top: if equal, pop and continue; otherwise there is no move (branch dies → reject).

• When input is finished and only the bottom marker remains, take an ε-move to the final state qf and accept.

This PDA accepts by final state (you can also accept by empty stack; both are standard).

Formal definition

$$M=(Q,\Sigma,\Gamma,\delta,q_0,z,F)$$

where

• $Q=\{q_0,q_1,q_f\}$
  

• $\Sigma=\{0,1,c\}$
  

• $\Gamma=\{0,1,z\}$ with $z$ the bottom-of-stack marker

• start state $q_0$, start stack symbol $z$
  

• $F=\{q_f\}$
  

Transition function $\delta$

Notation: $\delta(q,x,X)\ni (p,\gamma)$ means in state $q$ reading input symbol $x$ (or $x=\mathrm{\epsilon )\; with\; top }$$X$ go to $p$ and replace $X$ by $\gamma$. Replacing by the same symbol (e.g. 0→0) means effectively leave stack unchanged; $\mathrm{\epsilon \; means\; pop.}$

Only listed moves exist (all others are absent).

(Push phase: q0)

• $\delta (q_0,0,z)\ni (q_0,0z)\; —\; push\; 0\; above\; bottom\; marker.$

• $\delta(q_0,\,0,\,0)\ni (q_0,\,00)$ — push 0 on 0.

• $\delta(q_0,\,0,\,1)\ni (q_0,\,01)$ — push 0 on 1 (stack may have mixed symbols).

• $\delta (q_0,1,z)\ni (q_0,1z)—\; push\; 1\; above\; bottom.$

• $\delta(q_0,\,1,\,1)\ni (q_0,\,11)$ — push 1 on 1.

• $\delta(q_0,\,1,\,0)\ni (q_0,\,10)$ — push 1 on 0.

(These cover pushing 0 or 1 regardless of top symbol.)

(On the center symbol c: move to match phase without changing stack)

• $\delta(q_0,\,c,\,z)\ni (q_1,\,z)$
  

• $\delta(q_0,\,c,\,0)\ni (q_1,\,0)$
  

• $\delta (q_0,c,1)\ni (q_1,1)$

(Match/pop phase: q1) — each input symbol must match and pop top:

• $\delta(q_1,\,0,\,0)\ni (q_1,\,\varepsilon)$ — read 0 and pop a 0.

• $\delta(q_1,\,1,\,1)\ni (q_1,\,\varepsilon)$— read 1 and pop a 1.

(If the input symbol does not equal the stack top, no transition exists → reject.)

(When stack is back to bottom and input finished: accept)

• $\delta(q_1,\,\varepsilon,\,z)\ni (q_f,\,z)$
  

(That ε-move moves to the accepting state when input is consumed and the stack contains only z.)

Worked trace (example)

Take $w=101$. Then input string is 101 c 101. Start stack is z.

1. $(q_0,101c101,z)$

2. read 1: push → $(q_0,\;01c101,\;1z)$
   

3. read 0: push → $(q_0,1c101,01z)\; (top\; at\; right:\; top=0)$

4. read 1: push → $(q_0,\;c101,\;101z)$ (stack top is 1)

5. read c: move to match phase without changing stack → $(q_1,\;101,\;101z)$
   

6. read 1: top is 1 → pop → $(q_1,\;01,\;01z)$
   

7. read 0: top is 0 → pop → $(q_1,\;1,\;1z)$
   

8. read 1: top is 1 → pop → $(q_1,\;\varepsilon,\;z)$
   

9. input finished and stack top is z → ε-move to accept: $(q_f,\;\varepsilon,\;z)$. Accepted.

If at any point a right-half symbol does not match the stack-top, e.g. stack top=0 but input symbol is 1, there is no transition and the branch dies — string rejected.

Input : 1 0 1 0 1 0 1 0 1
Output :ACCEPTED

Input : 1 0 1 0 1 1 1 1 0
Output :NOT ACCEPTED

1. Construct Pushdown Automata for given languages
2. Construct Pushdown Automata for all length palindrome
3. NPDA for accepting the language L = {an bm cn| m,n>=1}
4. NPDA for accepting the language L = {an bn cm | m,n>=1}
5. NPDA for accepting the language L = {anbn | n>=1}
6. NPDA for accepting the language L = {am b(2m) | m>=1}
7. NPDA for accepting the language L = {am bn cp dq| m+n=p+q ; m,n,p,q>=1}
8. Construct Pushdown automata for L = {0n1m2m3n | m,n ? 0}
9. Construct Pushdown automata for L = {0n1m2(n+m) | m,n ? 0}
10. NPDA for accepting the language L = {ambnc(n+m) | m,n ? 1}
11. NPDA for accepting the language L = {amb(n+m)cn| m,n ? 1}
12. NPDA for accepting the language L = {a2mb3m | m ? 1}
13. NPDA for accepting the language L = {amb(2m+1) | m ? 1}
14. NPDA for accepting the language L = {aibjckdl | i==k or j==l,i>=1,j>=1}
15. Construct Pushdown automata for L = {a(2*m)c(4*n)dnbm | m,n ? 0}
16. Construct Pushdown automata for L = {0n1m2(n+m) | m,n ? 0}
17. NPDA for L = {0i1j2k | i==j or j==k ; i , j , k >= 1}
18. NPDA for accepting the language L = {anb(2n) | n>=1} U {anbn | n>=1}
19. NPDA for the language L ={w?{a,b}*| w contains equal no. of a’s and b’s}