\begin{frame}{Pumping Lemma Example}
    The \emph{pumping lemma} can be used to prove that a language is \emph{not regular}.
    Assume that $L = \{\, w \in \{a,b\}^* \mid w = w^R \,\}$ is regular.
    By the pumping lemma there exists $m>0$ such that
      \mpause[1]{a^mba^m} = xyz
    with $|xy| \leq m$, $|y| \geq 1$, and $xy^i z \in L$ for every $i \geq 0$.
    Since $|xy| \leq m$ and $|y|\geq 1$, it follows that
      x=a^{\,j} &&\text{and}&& y = a^k
    with $j\geq 0$ and $k\geq 1$.
    However $xyyz = a^{m+k} b a^m \not\in L$. \pause Contradiction!
    Thus $L$ is not regular.\qed