Library

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.

pushpopdone
The machine as drawn — 3 states, 8 transitions.

The author’s examples, run

ε → acceptabba → acceptaa → acceptaaaabbaaaa → acceptbbba → rejectba → rejectbaaabbaaaa → rejectab → reject