---
title: "PDA for palindromes over {a,b}"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:pda-palindrome-ab"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pda-palindrome-ab
site: BCT Engineering
---

# PDA for palindromes over {a,b}

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2070 Chaitra
- Video: [Pushdown Automata Example - Even Palindrome (Part 1)](https://www.youtube.com/watch?v=TEQcJybMMFU) — Neso Academy
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_3/theory_of_computation/pda-palindrome-ab
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Design a PDA that accepts all palindromes defined over {a, b}*.

## Short answer

Push each symbol onto stack. Nondeterministically guess the middle by an epsilon-transition (even length) or skip one symbol (odd). Then match and pop. Accept if Z0 remains at end.

## Answer

A palindrome reads the same forwards and backwards: wwᴿ (even length) or w a wᴿ / w b wᴿ (odd length, middle symbol a or b), including ε.

**Idea (nondeterministic):** push the first half onto the stack. At a guessed middle point, move to a second state (for odd length, skip the middle symbol). Then match each input symbol with the stack top, popping.

M = ({q0, q1, qf}, {a, b}, {a, b, Z0}, δ, q0, Z0, {qf}), with X standing for any of a, b, Z0.

| # | Transition | Meaning |
|---|---|---|
| 1 | δ(q0, a, X) ∋ (q0, aX) | push a |
| 2 | δ(q0, b, X) ∋ (q0, bX) | push b |
| 3 | δ(q0, ε, X) = {(q1, X)} | guess middle (even length) |
| 4 | δ(q0, a, X) ∋ (q1, X) | middle symbol a (odd length), not pushed |
| 5 | δ(q0, b, X) ∋ (q1, X) | middle symbol b (odd length), not pushed |
| 6 | δ(q1, a, a) = {(q1, ε)} | match a |
| 7 | δ(q1, b, b) = {(q1, ε)} | match b |
| 8 | δ(q1, ε, Z0) = {(qf, Z0)} | accept |

```text
   a,X/aX  b,X/bX             a,a/ε  b,b/ε
      ↺        ε,X/X                 ↺
 ──► (q0) ─────────────► (q1) ──ε,Z0/Z0──► ((qf))
        └── a,X/X or b,X/X ──►
            (skip odd middle)
```

Rules 1 and 4 (and 2 and 5) give two choices on the same input, e.g. δ(q0, a, X) = {(q0, aX), (q1, X)}; the PDA is **non-deterministic**, and a string is accepted if **some** sequence of choices works.

**Examples**
- abba: push a, b; guess the middle by an ε-move; read b (pop b), a (pop a); Z0 is exposed, accept.
- aba: push a; read b as the middle (no push); read a (pop a); accept.
- ab: push a; neither choice can match b against a, so it is rejected.
- ε: q0 → q1 by an ε-move → qf, accepted.

A PDA is needed (not a finite automaton) because the machine must remember the whole first half, whose length is unbounded.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. How does the PDA accept palindromes?
   A. Push every symbol and pop all at the end
   B. Push the first half, guess the middle, then match each input symbol against the stack top
   C. Count a's and b's
   D. Use states only
   Answer: B. The second half must be the reverse of the first, which a stack provides. (Key point: Core idea)

2. Why is the PDA non-deterministic?
   A. It has many states
   B. It has a stack
   C. It must guess where the middle is
   D. It reads ε
   Answer: C. The machine cannot know the midpoint, so it chooses between pushing and switching; acceptance needs only one successful path. (Key point: Nondeterminism)

3. How is the middle symbol of an odd palindrome handled?
   A. It is pushed twice
   B. It is read and skipped (not pushed) while moving to the matching state
   C. It is popped
   D. It is rejected
   Answer: B. Transitions 4 and 5 consume the middle symbol without pushing it. (Key point: Odd length)

4. Why can't a finite automaton accept palindromes?
   A. Palindromes are finite
   B. It must remember an unbounded first half
   C. It has no start state
   D. It cannot read b
   Answer: B. The first half has unbounded length, needing unbounded memory such as a stack. (Key point: Why PDA)

## Related in Theory of Computation

- [TM configuration; TM for palindromes](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-config-palindrome) — Theory of Computation, chapter 4
- [PDA configuration; PDA for a^(3n)b^n](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-config-a3n-bn) — Theory of Computation, chapter 3
- [PDA for aⁿb^(3n)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-b3n) — Theory of Computation, chapter 3
- [PDA for a^n b^(n+m) c^m](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-bm-cm-n-plus) — Theory of Computation, chapter 3
- [PDA for aⁱbʲcᵏ with i = j + k](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-i-equals-j-plus-k) — Theory of Computation, chapter 3
- [PDA for aⁿb^(2n+1)](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Apda-an-b2n-plus-1) — Theory of Computation, chapter 3

## Related in other subjects

- [Initial line design for 200 MW over 120 km](https://www.bctengineer.com/question.md?key=semester_8%2Ftransmission_and_distribution_system_design%3Aline-design-200mw-120km) — Transmission and Distribution System Design, chapter 2
- [Design FSA accepting even number of a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-even-number-of-a) — Discrete Structure, chapter 2, asked 4×
- [Design FSA accepting odd number of b's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-odd-number-of-b) — Discrete Structure, chapter 2, asked 4×
- [Define FSM; design FSA with two consecutive a's](https://www.bctengineer.com/question.md?key=semester_4%2Fdiscrete_structure%3Afsa-two-consecutive-a) — Discrete Structure, chapter 2, asked 4×