We can define a restricted npda as one that can increase the length of the stack by at most one
symbol in each move, changing Definition 7.1 so that
$\delta :$Q x $(\sum \cup$ {$\lambda$}$) $ × $ \Gamma \rightarrow 2^{Q ×(\Gamma \Gamma \cup \Gamma \cup {\lambda})}$
The interpretation of this is that the range of $δ$ consists of sets of pairs of the form $(q_i, ab), (q_i,a),$ or $(q_i, λ)$. Show that for every npda $M$ there exists such a restricted npda $\widehat{M}$ such that $L (M) = L(\widehat M$) .
----------------------------------------------------------------------------------------------------------
Definition 7.1: A nondeterministic pushdown accepter (npda) is defined by the septuple
$M=(Q,\sum,\Gamma,\delta,q_0,z,F)$
where,
$Q$ is a finite set of internal states of the control unit,
$Σ$ is the input alphabet,
$Γ$ is a finite set of symbols called the stack alphabet,
$δ : Q × (Σ ∪$ {$λ$}$) × Γ →$ set of finite subsets of $Q × Γ^*$ is the transition function,
$q_0 ∈ Q$ is the initial state of the control unit,
$z ∈ Γ$ is the stack start symbol,
$F ⊆ Q$ is the set of final states.
