\begin{frame}{From Final States to Acceptance with Empty Stack} \begin{goal}{} Every NPDA $M$ be transformed into NPDA $N$ such that \begin{itemize} \item it has \emph{a single final state} $F = \{\,q_f\,\}$, \item \emph{final state is reached if and only if the stack is empty}, \item $L(M) = L(N) = L_\lambda(N)$. \end{itemize} \end{goal} \pause \begin{block}{} We add fresh states $\{\,\alert{\widehat{q_0},q_e,q_f}\,\}$ to $Q$ and stack element $\alert{\hat{z}}$ to $\Gamma$. \begin{itemize}\setlength{\itemsep}{-0.5ex} \pause \item Add a transition $\widehat{q_0} \stackrel{\lambda[z/z\hat{z}]}{\longrightarrow} q_0$.\\ (Intuition: $\hat{z}$ marks the bottom of the stack.) \pause \item Add transitions $q \stackrel{\lambda[s/s]}{\longrightarrow} q_e$ for every $q \in F$, $s \in \Gamma$. \pause \item Add transitions $q_e \stackrel{\lambda[s/\lambda]}{\longrightarrow} q_e$ for every $s \in \Gamma \setminus \{\hat{z}\}$.\\ (Intuition: $q_e$ empties the stack.) \pause \item Add transition $q_e \stackrel{\lambda[\hat{z}/\lambda]}{\longrightarrow} q_f$.\\ (Intuition: switch to final state $q_f$ when stack is empty.) \pause \item Define $\widehat{q_0}$ as starting state and $F = \{\, q_f \,\}$. \end{itemize} \end{block} \end{frame}