\begin{frame}{Exercise} \begin{exampleblock}{} Transform the following context-free grammar \begin{talign} S &\to aSbX \mid a\\ X &\to Xa \mid aba \end{talign} into Chomsky normal form. \medskip The $\lambda$-rules and unit-rules have already been removed. \pause\medskip We continue the transformation: \begin{talign} S &\to \alt<-6>{\alt<-3>{aSbX}{C_aSC_bX}}{C_aS_2} \mid a & \mpause[5]{S_2 &\to SS_3 & S_3 &\to C_bX}\\ X &\to \alt<-4>{Xa}{XC_a} \mid \alt<-7>{\alt<-5>{aba}{C_aC_bC_a}}{C_aX_2} & \mpause[6]{X_2 &\to C_bC_a} \\ \mpause[1]{C_a &\to a} \\ \mpause[1]{C_b &\to b} \hspace{2.5cm} \mpause{} \mpause{}\mpause{}\mpause{}\mpause{} \end{talign} \end{exampleblock} \end{frame}