NPDA · Context-free
Palindromes: guess the middle
Accepts even-length palindromes over {a,b}. The machine pushes symbols, nondeterministically guesses where the middle is, then pops and matches the mirror half.
The author’s examples, run
abba → acceptbaab → acceptabaaba → acceptabab → rejectaba → reject