\begin{frame}{Pumping Lemma Example}
  \begin{goal}{}
    The \emph{pumping lemma} can be used to prove that a language is \emph{not regular}.
  \end{goal}
  \pause
  
  \begin{exampleblock}{}
    Assume that $L = \{\, w \in \{a,b\}^* \mid w = w^R \,\}$ is regular.
    \pause\medskip
    
    By the pumping lemma there exists $m>0$ such that
    \begin{talign}
      \mpause[1]{a^mba^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 $xyyz = a^{m+k} b a^m \not\in L$. \pause Contradiction!
    \pause\medskip
    
    Thus $L$ is not regular.\qed
  \end{exampleblock}
\end{frame}