Extended PushDown Automaton transitions

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

Rendered by QuickLaTeX.com

The above transition is read as follows. Read a, pop x from the top of the stack and push vyz onto the top of the stack.

Keep in mind that the rightmost symbol is pushed first. So z is pushed first, then y and then v.

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 a, x \rightarrow y_1 y_2 \cdots y_n as an extended PDA transition. A equivalent set of PDA transitions will be

    \begin{align*} a, x &\rightarrow y_n \\ \epsilon, \epsilon &\rightarrow y_{n-1} \\ \vdots \\ \epsilon, \epsilon &\rightarrow y_{2} \\ \epsilon, \epsilon &\rightarrow y_{1} \\ \end{align*}

Thus extended PDAs and PDAs recognize the same set of languages.

1 Comment Extended PushDown Automaton transitions

  1. Pingback: Converting a Context-Free Grammar to a PushDown Automaton - TheBeardSage

Leave a Reply

Your email address will not be published. Required fields are marked *