Pushdown Automaton - Generalized Pushdown Automaton (GPDA)

Generalized Pushdown Automaton (GPDA)

A GPDA is a PDA which 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:

where Q, q₀ and F are defined the same way as a PDA.

:

is the transition function.

Computation rules for a GPDA are the same as a PDA except that the a_i+1's and b_i+1'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 (q₁, w, x₁x₂...x_m) (q₂, y₁y₂...y_n) be a transition of the GPDA

where, .

Construct the following transitions for the PDA:

(q₁, w, x₁) (p₁, )

(p₁, x₂) (p₂, )

(p_m-1, x_m) (p_m, )

(p_m, ) (p_m+1, y_n)

(p_m+1, ) (p_m+2, y_n-1)

(p_m+n-1, ) (q₂, y₁)