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