\begin{frame}{Removal of Lambda Rules} \begin{goal}{Theorem} For every context-free language $L$ there exists a context-free grammar $G$ \alert{without $\lambda$-rules} such that $L(G) = L \alert{\setminus \{\lambda\}}$. \end{goal} \pause \begin{construction} Let $G$ be a context-free grammar with $L(G) = L$. \begin{itemize} \pause \item Determine all erasable variables (that is, variables $A \Rightarrow^* \lambda$). \pause \item For every rule \alert{$A \to xBy$ with $B \Rightarrow^* \lambda$}, add a rule \alert{$A \to xy$}. \pause \item Remove all $\lambda$-production rules. \end{itemize} \pause The resulting grammar $G$ has the property \alert{$L(G) = L \setminus \{\lambda\}$}. \end{construction} \end{frame}