\begin{frame}{From Acceptance with Empty Stack To Final States}
  \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_{\alert{\lambda}}(M) = L(N) = L_\lambda(N)$.
    \end{itemize}
  \end{goal}
  \pause
  
  \begin{block}{}
    We add fresh states $\{\,\alert{\widehat{q_0},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 transition $q \stackrel{\lambda[\hat{z}/\lambda]}{\longrightarrow} q_f$ for every state $q \in Q \setminus \{\, \widehat{q_0},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}