In DFA/NFA the automaton halts when it finishes reading the string.
In a PDA there's the string and the stack. When the string is finished and there are symbols on the stack does it ignore them? Or does it have to pop them?
Or maybe does the behavior depend on whether the PDA is deterministic or not?
Here's an example to demonstrate where the ambiguity is.
It's a dumb example and it can be done with a DFA but just for demonstration.
This PDA should accept anything but the string
It starts by inserting a
$ to mark the bottom of the stack. Then it inserts 2
as. Then when it receives an a it pops one from a stack. It can do that twice.
Now at this point suppose that the input string was indeed
aa, and that the machine reached state
x and popped the two
as. Now the stack has only
$ in it.
Does it have to go to the next state (
y) because there's a
$on top of the stack?
Or by non-determinism can it be either in
If the latter is true then this is a wrong PDA for this language. It would accept everything.