Extended PushDown Automatons are an extension of PushDown Automatons. The extension is that it can push any finite number of stack symbols in a single transition.
Rightmost First
The above transition is read as follows. Read , pop
from the top of the stack and push
onto the top of the stack.
Keep in mind that the rightmost symbol is pushed first. So is pushed first, then
and then
.
Conversion to PDA
Every extended PDA transition can be converted into a set of PDA transitions. Just emulate the stack operations from right to left.
Consider as an extended PDA transition. A equivalent set of PDA transitions will be
Thus extended PDAs and PDAs recognize the same set of languages.
Pingback: Converting a Context-Free Grammar to a PushDown Automaton - TheBeardSage