23/93
\begin{frame}{Drawing Pushdown Automata}
  \begin{goal}{}
    The transition graph for a NPDA contains 
    \begin{talign}
      \text{for every \alert{$(q',v) \in \delta(q,\alpha,b)$}} &&
      \text{an arrow \alert{$q \stackrel{\alpha[b/v]}{\longrightarrow} q'$}.}
    \end{talign}
  \end{goal}
  \pause
    
  \begin{exampleblock}{}
    We construct NPDA $M$ with $L(M) = \{\, a^n b^n \mid n \geq 0\, \}$.
    \pause
    \begin{talign}
      Q &=\{q_0,q_1,q_2\} & 
      \Sigma &=\{a,b\} & 
      \Gamma &= \{0,1\} &
      z &= 0 &
      F &= \{q_2\}
    \end{talign}
    \pause
    Intuition:
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item In \alert{$q_0$} a stack \alert{$1^k0$} means: we have read $k$ $a$'s.
      \item In \alert{$q_1$} a stack \alert{$1^k0$} means: we still have to read $k$ $b$'s.
    \end{itemize}
    \pause
    \vspace{-2ex}
    \begin{center}
      \input{tikz/npda1.tex}
    \end{center}
    \vspace{-2.5ex}
  \end{exampleblock}
  \bigskip
\end{frame}