\begin{frame}{Chomsky Normal Form}
  \begin{construction}
    Let $G$ be a context-free grammar without $\lambda$- and unit-productions
    and $L(G)=L \setminus \{\lambda\}$ .
    \pause\medskip
    
    \begin{itemize}
      \item 
        Introduce variables \alert{$C_a$} and rules \alert{$C_a \to a$} for every $a \in T$.
    \pause\medskip
      \item 
        Replace every rule $A\to x_1\cdots x_n$ ($x_i\in V\cup T$) \alert{with $n \ge 2$} by
        \begin{talign}
          \alert{A \to \sigma(x_1)\cdots \sigma(x_n)} &&
          \text{where} &&
          \alert{\sigma(x) =} 
          \begin{cases}
            \alert{x}, &\text{if $x \in V$}\\
            \alert{C_{x}}, &\text{if $x \in T$}
          \end{cases}
        \end{talign}
    \pause
      \item 
        Replace every $A \to B_1\cdots B_n$ with $n\geq 3$ by
        \begin{talign}
          \alert{A} &\alert{\to} \alert{B_1\cdots B_{n-2} C} &
          \alert{C} &\alert{\to} \alert{B_{n-1} B_n}
        \end{talign}
        where $C$ is a fresh variable.
    \end{itemize}
    \pause\medskip
    
    Repeat the last step until all rules are in Chomsky normal form.
  \end{construction}
\end{frame}