24/103
\begin{frame}{Pumping Lemma as a Game}
  \begin{goal}{}
  To \emph{contradict the pumping lemma}, we prove the negation:
    \begin{talign}
      &\alert{\forall} m>0.\\[-.5ex]
      &\qquad \alert{\exists} w\in L \text{ with } |w|\geq m.\\[-.5ex]
      &\qquad\qquad \alert{\forall} u,v,x,y,z \text{ with } w=uvxyz,\; |vxy| \leq m,\; |vy|\geq 1.\\[-.5ex]
      &\qquad\qquad\qquad \alert{\exists} i \geq 0.\, uv^ixy^iz \alert{\not\in} L
    \end{talign}
  \end{goal}

  \begin{block}{Pumping Lemma as a Game}
    Given is a language $L$. \pause We want to prove that $L$ is not context-free.
    \begin{enumerate}
    \pause
      \item Opponent picks \alert{$m$}.
    \pause
      \item We choose a word \alert{$w\in L$} with $|w|\geq m$.
    \pause
      \item Opponent picks \alert{$u,v,x,y,z$} \\with $w=uvxyz$, $|vxy|\leq m$ and $|vy|\geq 1$.
    \pause
      \item If we can find \alert{$i\geq 0$} such that \alert{$uv^ixy^iz\not\in L$}, then \emph{we win}.
    \end{enumerate}
    \pause
    If we can always win, then $L$ does not fulfil the pumping lemma! 
  \end{block}
\end{frame}