NPDA · Context-free
Every palindrome, odd or even
A palindrome reads the same backwards. Push the first half, guess where the middle is — either between two letters or on a letter that has no partner — and pop the second half against the first. One guess too many letters early or late and the stack does not empty at the end.
The author’s examples, run
ε → acceptabba → acceptaa → acceptaaaabbaaaa → acceptbbba → rejectba → rejectbaaabbaaaa → rejectab → reject