PDA for palindromes over {a,b}

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.

   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.