\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}