\begin{frame}{Exercises (3)}
  \begin{exampleblock}{}
    Show that $L = \{\,\ ww \mid w\in\{a,b\}^* \,\}$ is not context-free.
    \pause\medskip
    
    Assume that $L$ was context-free.
    \pause\medskip
    
    According to the pumping lemma there is $m>0$ such that
    \begin{talign}
      \mpause[1]{a^mb^ma^mb^m} = uvxyz
    \end{talign}
    with $|vxy| \leq m$, $|vy| \geq 1$, and $uv^ixy^i z \in L$ for every $i \geq 0$.
    \pause\pause\medskip

    Since $|vxy| \leq m$, \alert{$vy = a^{\,j}b^k$} or \alert{$vy = b^ka^{\,j}$} for some $j,k \ge 0$.
    \pause\medskip
    
    Since $|vy|\geq 1$ we have \alert{$j+k \geq 1$}.
    \pause\medskip

    Since $|vxy| \leq m$, we have:
    \begin{itemize}
    \pause
      \item If $|u| < m$, then \alert{$uv^0xy^0z = a^{m-j}b^{m-k}a^{m}b^{m} \not\in L$}.
    \pause
      \item If $m \le |u| < 2m$, then \alert{$uv^0xy^0z = a^{m}b^{m-k}a^{m-j}b^{m} \not\in L$}.
    \pause
      \item If $2m \le |u|$, then \alert{$uv^0xy^0z = a^{m}b^{m}a^{m-j}b^{m-k} \not\in L$}.
    \end{itemize}
    \pause
    \alert{Contradiction in each case!} Thus $L$ is not context-free.
  \end{exampleblock}
\end{frame}