\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}