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