At any time the state of a PDA
is given by:
We define a relation
between IDs
which describes how the PDA can change from one ID to the next one.
Since PDAs in general are nondeterministic this is a relation (not a
function), i.e. there may be more than one possibility.
There are two possibilities for :
In the second case the PDA ignores the input and silently moves into a new state and modifies the stack as above. The input is unchanged.
Consider the word -- what are possible sequences of IDs for
starting with
?
However, this is not the only possible sequence of IDs for this input. E.g. the PDA may just guess the middle wrong:
If we start with a word which is not in the language
(like
) then the automaton will always get stuck before
reaching a final state.