32/103
\begin{frame}{Example}
  \begin{exampleblock}{}
    Assume that $L = \{\,a^n b^n c^n \mid n \geq 0\,\}$ was context-free.
    \pause\medskip
    
    According to the pumping lemma there is $m>0$ such that
    \begin{talign}
      a^mb^mc^m = uvxyz
    \end{talign}
    with $|vxy| \leq m$, $|vy| \geq 1$, and $uv^ixy^i z \in L$ for every $i \geq 0$.
    \pause\medskip

    \emph{Note:} 
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item opponent picks $m$,
      \item \alert{we pick $w = a^mb^mc^m$},
      \item opponent $u,v,x,y,z$.
    \end{itemize}
    \pause
    We do not know $u,v,x,y,z$, but we can reason about them:
    \begin{itemize}\setlength{\itemsep}{0pt}
    \pause
      \item Since $|vxy| \leq m$, it follows that $vy = a^{\,j}b^k$ or $vy = b^{\,j}c^k$.
    \pause
      \item Since $|vy|\geq 1$ we have $j+k \geq 1$.
    \end{itemize}
    \pause

    Then \alert{$uv^2xy^2z$} does not contain equally many $a$'s, $b$'s and $c$'s.
    \pause\medskip

    \alert{Contradiction}, thus $L$ is not context-free.
  \end{exampleblock}
\end{frame}