\begin{frame}{Exercise (1)} \begin{exampleblock}{} Use the pumping lemma to \emph{show that} \begin{talign} L = \{\,a^nb^n\mid n\geq 0\,\} \end{talign} \emph{is not regular}. \pause Assume that $L$ was regular. \pause\medskip By the pumping lemma there exists $m>0$ such that \begin{talign} \mpause[1]{a^m b^m} = xyz \end{talign} with $|xy| \leq m$, $|y| \geq 1$, and $xy^i z \in L$ for every $i \geq 0$. \pause\pause\medskip Since $|xy| \leq m$ and $|y|\geq 1$, it follows that \begin{talign} x=a^{\,j} &&\text{and}&& y = a^k \end{talign} with $j\geq 0$ and $k\geq 1$. \pause\medskip However $xy^0z = xz = a^{m-k} b^m \not\in L$. \pause Contradiction! \pause\medskip Thus $L$ is not regular.\qed \end{exampleblock} \end{frame}