54/216
\begin{frame}{Removal of Unit Production Rules}
\begin{block}{}
A rule $A \to B$ is called \emph{unit production rule} (here $B \in V$).
\end{block}
\pause\medskip

\begin{block}{Theorem}
For every context-free language $L$
there is a context-free grammar $G$
\alert{without $\lambda$- and unit-productions} with $L(G) = L \setminus \{\lambda\}$.
\end{block}
\pause

\begin{construction}
Let $G$ be context-free, without $\lambda$-rules, and $L(G) = L \setminus \{\lambda\}$.
\pause\medskip

Determine all pairs $A \neq B$ with \alert{$A \Rightarrow^+ B$}.
\pause\medskip

Whenever \alert{$A \Rightarrow^+ B$} and \alert{$B \to y$} is a rule, add a rule \alert{$A \to y$}.
\pause\medskip

Remove all unit production rules.
\pause\medskip

The resulting grammar $G$ has no $\lambda$- and unit-productions and
it has the property \alert{$L(G)= L \setminus \{\lambda\}$}.
\end{construction}
\end{frame}