A pushdown automaton
is given
by the following data
As an example we consider a PDA which recognizes the language of even
length palindromes over
--
. Intuitively, this PDA pushes the input symbols on
the stack until it guesses that it is in the middle and then it
compares the input with what is on the stack, popping of symbols from
the stack as it goes. If it reaches the end of the input precisely at
the time when the stack is empty, it accepts.
To save space we may abbreviate this by writing: