---
title: "PDA for wwᴿ; accept abbbba"
subject: "Theory of Computation"
chapter: 3
key: "semester_3/theory_of_computation:pda-wwr-abbbba"
source: https://www.bctengineer.com/q/semester_3/theory_of_computation/pda-wwr-abbbba
site: BCT Engineering
---

# PDA for wwᴿ; accept abbbba

Theory of Computation · Chapter 3: Context Free Grammar

- Asked in: 2072 Kartik
- Video: [Construct pda for WW^r | NPDA for WW^r | PDA for Even Palindrome | TOC | Automata Theory](https://www.youtube.com/watch?v=0xQKmUt5p94) — THE GATEHUB
- 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-wwr-abbbba
- Whole chapter: https://www.bctengineer.com/md/semester_3/theory_of_computation/chapter-3

## Question

Design a PDA to accept L = {wwᴿ : w ∈ {a,b}*}. Show how it accepts "abbbba".

## Short answer

Push symbols, nondeterministically guess midpoint by epsilon, then pop matching symbols. For abbbba, push a,b,b; after epsilon, pop b,b,a; stack returns to Z0, accepted.

## Answer

L = { wwᴿ : w ∈ {a,b}* } is the set of even-length palindromes over {a, b} (the second half is the reverse of the first half).

**Idea:** push the first half; at a non-deterministically guessed midpoint switch to matching mode, popping one symbol per input symbol.

M = ({q0, q1, qf}, {a, b}, {a, b, Z0}, δ, q0, Z0, {qf}), X = 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 the middle |
| 4 | δ(q1, a, a) = {(q1, ε)} | match a |
| 5 | δ(q1, b, b) = {(q1, ε)} | match b |
| 6 | δ(q1, ε, Z0) = {(qf, Z0)} | accept |

```text
   a,X/aX  b,X/bX             a,a/ε  b,b/ε
       ↺                           ↺
  ──► (q0) ───── ε,X/X ─────► (q1) ──ε,Z0/Z0──► ((qf))
```

#### Processing abbbba (w = abb, wᴿ = bba)
```text
(q0, abbbba, Z0)
⊢ (q0, bbbba, aZ0)      push a
⊢ (q0, bbba,  baZ0)     push b
⊢ (q0, bba,   bbaZ0)    push b
⊢ (q1, bba,   bbaZ0)    ε: guess the middle
⊢ (q1, ba,    baZ0)     b matches b, pop
⊢ (q1, a,     aZ0)      b matches b, pop
⊢ (q1, ε,     Z0)       a matches a, pop
⊢ (qf, ε,     Z0)       accept
```
**abbbba is accepted.** Other guesses of the middle (after 0, 1, 2, 4, 5 or 6 symbols) fail to match and die, which is allowed in a non-deterministic PDA since one accepting path exists.

## Check yourself

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

1. What is L = {wwᴿ}?
   A. Odd-length palindromes
   B. Even-length palindromes
   C. All strings of a and b
   D. Strings with equal a's and b's
   Answer: B. The second half is the reverse of the first, so the length is even. (Key point: Language)

2. How does the PDA find the middle of the string?
   A. It counts the length first
   B. It uses the ε-move δ(q0, ε, X) = (q1, X) to non-deterministically guess it
   C. It looks for a special marker
   D. It always switches after 3 symbols
   Answer: B. No marker exists, so a non-deterministic ε-move switches from push to match mode. (Key point: Guessing midpoint)

3. In state q1, what must happen on reading a symbol?
   A. It is pushed
   B. It must equal the stack top, which is popped
   C. It is ignored
   D. It empties the stack
   Answer: B. Rules 4 and 5 pop a only on a and b only on b. (Key point: Matching)

4. What is the stack after pushing the first half of abbbba?
   A. abbZ0 with a on top
   B. aabbZ0
   C. bbaZ0 (top is b)
   D. abZ0
   Answer: C. Pushing a, b, b leaves b on top: bbaZ0, matching the remaining bba. (Key point: Trace abbbba)

## Related in Theory of Computation

- [TM accepting wwᴿ; process 101101](https://www.bctengineer.com/question.md?key=semester_3%2Ftheory_of_computation%3Atm-accept-wwr-101101) — 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

- [Design: 125 kVA 6600/400 V three phase transformer](https://www.bctengineer.com/question.md?key=semester_5%2Felectric_machine_design%3Adesign-125kva-three-phase-windings) — Electric Machine Design, chapter 3, asked 4×
- [Design: 100 kVA 11/132 kV transformer with winding data](https://www.bctengineer.com/question.md?key=semester_5%2Felectric_machine_design%3Adesign-100kva-11-132kv) — Electric Machine Design, chapter 3, asked 3×
- [Design: 25 kVA transformer frame, regulation, tubes](https://www.bctengineer.com/question.md?key=semester_5%2Felectric_machine_design%3Adesign-25kva-cooling-tubes) — Electric Machine Design, chapter 3, asked 2×
- [Return period for bridge design at 5% risk](https://www.bctengineer.com/question.md?key=semester_5%2Fengineering_hydrology%3Abridge-return-period-5pct-risk) — Engineering Hydrology, chapter 6