Next: How does a PDA
Up: Pushdown automata
Previous: Pushdown automata
A pushdown automaton
is given
by the following data
- A finite set of states,
- A finite set of symbols (the alphabet),
- A finite set of stack symbols,
- A transition function
Here
are the finite subsets of a set, i.e. this can be
defined as
- An initial state ,
- An initial stack symbol
,
- A set of final states
.
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.
where is given by the following equations:
To save space we may abbreviate this by writing:
where
. We obtain the previous table by
expanding all the possibilities for .
Next: How does a PDA
Up: Pushdown automata
Previous: Pushdown automata
Thorsten Altenkirch
2001-05-08