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