Editing Pushdown automaton (section)

==Generalization==

A generalized pushdown automaton (GPDA) is a PDA that writes an entire string of some known length to the stack or removes an entire string from the stack in one step.

A GPDA is formally defined as a 6-tuple: 
:<math>M=(Q,\  \Sigma,\  \Gamma,\  \delta, \ q_{0}, \ F)</math>
where <math>Q, \Sigma\,, \Gamma\,, q_0</math>, and {{tmath|F}} are defined the same way as a PDA.
:<math>\,\delta</math>: <math>Q \times  \Sigma_{\epsilon}  \times \Gamma^{*} \longrightarrow P( Q \times \Gamma^{*} )</math>
is the transition function.

Computation rules for a GPDA are the same as a PDA except that the <math>a_{i+1}</math>'s and <math>b_{i+1}</math>'s are now strings instead of symbols.

GPDA's and PDA's are equivalent in that if a language is recognized by a PDA, it is also recognized by a GPDA and vice versa.

One can formulate an analytic proof for the equivalence of GPDA's and PDA's using the following simulation:

Let <math>\delta (q_{1}, w, x_{1} x_{2} \cdot x_{m}) \longrightarrow (q_{2}, y_{1} y_{2}...y_{n})</math> be a transition of the GPDA

where <math>q_1, q_2 \in Q, w \in\Sigma_{\epsilon}, x_1, x_2,\ldots,x_m\in\Gamma^{*}, m\geq 0, y_1, y_2,\ldots, y_n\in\Gamma^{*}, n\geq 0</math>.

Construct the following transitions for the PDA:

:<math>\begin{array}{lcl}
\delta'(q_{1}, w, x_{1}) &\longrightarrow& (p_{1}, \epsilon)
\\
\delta'(p_{1}, \epsilon, x_{2}) &\longrightarrow& (p_{2}, \epsilon)
\\
&\vdots&
\\
\delta'(p_{m-1}, \epsilon, x_{m}) &\longrightarrow& (p_{m}, \epsilon)
\\
\delta'(p_{m}, \epsilon, \epsilon ) &\longrightarrow& (p_{m+1}, y_{n})
\\
\delta'(p_{m+1}, \epsilon, \epsilon ) &\longrightarrow& (p_{m+2}, y_{n-1})
\\
&\vdots&
\\
\delta'(p_{m+n-1}, \epsilon, \epsilon ) &\longrightarrow& (q_{2}, y_{1}).
\end{array}</math>