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.