There are two ways to define the language of a PDA
(
).
because there are two notions of acceptance:
In our example the PDA would accept
because
and
.
Hence we conclude
.
On the other hand since there is no successful sequence of IDs starting
with
we know that
.
If we specify a PDA for acceptance by empty stack we will leave out
the set of final states and just use
.
Our example automaton also works if we leave out
and use
acceptance by empty stack.
We can always turn a PDA which use one acceptance method into one which uses the other. Hence, both acceptance criteria specify the same class of languages.