\begin{frame}{Pumping Lemma for Context-Free Languages (1961)}
  \begin{goal}{Theorem}
    Let $L$ be a context-free language. 
    \medskip
    
    There exists $m>0$ such that
    for every word $w \in L$ with \alert{$|w| \geq m$}:
    \begin{talign}
      \alert{w = uvxyz}
    \end{talign}
    with \alert{$|vxy| \leq m$} and \alert{$|vy| \geq 1$}, and
    \alert{$uv^ixy^i z \in L$} for every $i \geq 0$.
  \end{goal}
  \pause
  
  \begin{block}{Proof}
    Let $G$ be a context-free grammar with $L(G) = L \setminus \{\lambda\}$
    \begin{itemize}\setlength{\itemsep}{0pt}
      \item with \alert{$k$} variables, and
      \item without $\lambda$ and unit productions.
    \end{itemize}
    \pause
    Let \alert{$m$} = 1 + maximum number of leaves of derivation trees of depth $\leq (k + 2)$.
    \medskip\pause
    
    \ \hfill continued on next slide\ldots 
  \end{block}
\end{frame}