14/103
\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 must be a path of length $> k$. 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+1$,
\pause
\item $\alert{|vy| \geq 1}$, since there are no $\lambda$ and unit productions.\hfill \qed
\end{itemize}
\end{block}
\end{frame}