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

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.

The Beard Sage

Extended PushDown Automaton transitions

Rightmost First

Conversion to PDA

1 Comment → Extended PushDown Automaton transitions

Leave a Reply Cancel reply