17/103
\begin{frame}{Using the Pumping Lemma}
  \begin{alertblock}{Attention}
    A contradiction of the pumping lemma for 
    specific values of $m$, or of $u,v,x,y,z$, is \alert{not sufficient}!
  \end{alertblock}  
  \pause
    
  \begin{goal}{}
    Pumping lemma as formula (\alert{note the quantifiers}):
    \begin{talign}
      &\exists m>0.\\[-.5ex]
      &\qquad \forall w\in L \text{ with } |w|\geq m.\\[-.5ex]
      &\qquad\qquad \exists u,v,x,y,z \text{ with } w=uvxyz,\; |vxy| \leq m,\; |vy|\geq 1.\\[-.5ex]
      &\qquad\qquad\qquad \forall i \geq 0.\, uv^ixy^iz\in L
    \end{talign}
  \end{goal}
  \pause

  \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}
\end{frame}