In class we defined PDAs as only being able to push a single symbol on the stack at

a time. That is$,$ we defined the transitions function $\backslash$delta as taking a state, an input, and a stack

element and outputting a new state and $($at most$)$ ONE stack element.

A generalized PDA allows popping more than one symbol and pushing more than one symbol

onto the stack in a single transition. That is$,$ we define a transition function as $\backslash$delta : Q $\backslash$times $\backslash$Sigma $\backslash$times

$\backslash$Gamma

$$

$->$ P$($Q $\backslash$times $\backslash$Gamma

$$

$$

$).$ For example, a transition $(0,00->111)$ would indicate that on input $0$ if

we pop $20$s from the stack we would push $31$s onto the stack.

Prove that generalized PDAs recognize the same set of languages as the PDAs described in

class