- 2072 Kartik
PDA for wwᴿ; accept 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.
Design a PDA to accept L = {wwᴿ : w ∈ {a,b}*}. Show how it accepts "abbbba".
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 |
a,X/aX b,X/bX a,a/ε b,b/ε
↺ ↺
──► (q0) ───── ε,X/X ─────► (q1) ──ε,Z0/Z0──► ((qf))
Processing abbbba (w = abb, wᴿ = bba)
(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.
✓ Answer checked by Claude Opus 5.5 (high effort)
Related questions
- TM accepting wwᴿ; process 101101 · Theory of Computation, chapter 4
- PDA configuration; PDA for a^(3n)b^n · Theory of Computation, chapter 3
- PDA for aⁿb^(3n) · Theory of Computation, chapter 3
- PDA for a^n b^(n+m) c^m · Theory of Computation, chapter 3
- PDA for aⁱbʲcᵏ with i = j + k · Theory of Computation, chapter 3
- PDA for aⁿb^(2n+1) · Theory of Computation, chapter 3
- Design: 125 kVA 6600/400 V three phase transformer · Electric Machine Design, chapter 3 · asked 4×
- Design: 100 kVA 11/132 kV transformer with winding data · Electric Machine Design, chapter 3 · asked 3×
- Design: 25 kVA transformer frame, regulation, tubes · Electric Machine Design, chapter 3 · asked 2×
- Return period for bridge design at 5% risk · Engineering Hydrology, chapter 6