\begin{frame}{Pumping Lemma for Context-Free Languages (1961)}
  \begin{block}{}
    Let $w \in L$ with $|w| \geq m$. 
    Consider a derivation tree for $w$.
    \pause\medskip
   
    There is a path of length $\ge k + 2$. Consider the longest path. 
    \pause\medskip
  
    As there are only $k$ variables, there must be 
    a variable $A$ that occurs twice among the last $k+1$ variable nodes of the path.
    \medskip
    
    \begin{minipage}{.39\textwidth}
    \begin{center}
      \input{pomp.pdf_t}
    \end{center}
    \end{minipage}  
    \begin{minipage}{.59\textwidth}
      \pause
      We have $w=uvxyz$ with
      \begin{itemize}
        \item \alert{$S \Rightarrow^* uAz$} 
        \item \alert{$A \Rightarrow^+ vAy$}
        \item \alert{$A \Rightarrow^+ x$}
      \end{itemize}
      \pause
      Hence
      \begin{itemize}
        \item \alert{$S \Rightarrow^+ uv^ixy^iz$} for every $i\geq 0$.
      \end{itemize}
    \end{minipage}
    \pause
    
    Then 
    \begin{itemize}
      \item $\alert{|vxy| \leq m}$ as the subtree generating $vxy$ has depth $\leq k+2$,
    \pause
      \item $\alert{|vy| \geq 1}$, since there are no $\lambda$ and unit productions.\hfill \qed
    \end{itemize}
  \end{block}  
\end{frame}