\begin{frame}{Non-Regular Languages}
  \begin{block}{Theorem}
    $L = \{\, a^n b^n \mid n \geq 0\, \} $ is \emph{not} regular.
  \end{block}
  \pause
  
  \begin{proof}
    For a contradiction, assume that $L$ was regular.
    \pause\medskip
    
    Then there exists a DFA $M = (Q,\{a,b\},\delta,q_0,F)$ with $L(M) = L$.
    \pause\medskip

    Because $Q$ is finite, we have
    \begin{talign}
      q_0 \apath{a^k} q \apath{a^\ell} q
    \end{talign}
    for some $\ell \ge 1$ and $q \in Q$.
    \pause
    Then for some $q' \in Q$ 
    \begin{talign}
      q_0 \apath{a^k} q \apath{b^k} q' &&
      q_0 \apath{a^k} q \apath{a^\ell} q \apath{b^k} q' &&
    \end{talign}
    \pause
    Then $q' \in F$ since \alert{$a^k b^k \in L$}. \pause However, $q' \not\in F$ since \alert{$a^{k+\ell} b^k \not\in L$}.\\
    \pause\medskip
    
    \alert{Contradiction}, thus $L$ is not regular.
  \end{proof}
  \pause
  
  We generalise the idea of the proof\ldots
\end{frame}