Library

DPDA · Deterministic context-free

A palindrome with its middle marked: wcwᴿ

When the centre is marked, a palindrome is easy for a deterministic machine: push until the c, then match each symbol against the top of the stack. Remove the c and the machine has to guess — see the NPDA that does.

pushmatchdone
The machine as drawn — 3 states, 6 transitions.

The author’s examples, run

c → acceptabcba → acceptaca → acceptbaabaacaabaab → accepta → rejectbbcba → rejectbca → rejectaaabaacaabaab → reject