Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form

Question

The grammar have the following producitons,

\begin{align} S&\rightarrow aTbS \mid\epsilon\\ T&\rightarrow aTb\mid\epsilon \end{align}

Already turned this homework in, but I need to convert this grammar to chomsky normal form. Our teacher didn't go over this very well and all the documentation doesn't make sense to me and they almost all over the same example. Can someone please help? I only understand the first step which is making a new start state go to $S$. I have a vague understanding that I have to remove the null terminations next.

Answer 1

Our grammar $G$ has following two production where $S$ is start symbol.

$S\rightarrow aTbS \vert\epsilon$

$T\rightarrow aTb|\epsilon$

Now to convert it to chomsky normal form (CNF) we have to perform following steps:

1. If there is some production having $S$ in it's right side($S\rightarrow aTbS$ in this example) then add new start symbol $S_0$ and production rule $S_0 \rightarrow S$ to $G$.

2. Then remove null production from $G$: So, after removing null production $G$ will have following productions:

   $S_0 \rightarrow S$

   $S \rightarrow aTbS|abS|aTb|ab$

   $T \rightarrow aTb|ab$

3. Now we have to remove unit production from $G$. But there are none of them.

4. Then if there is production containing both terminal and nonterminals on RHS then introduce new non-terminal for the terminal appearing there and replace occurence of terminal in that RHS by this non-terminal. example will make this clear.

   we, have this $S \rightarrow aTbS$ production. So we add production $A \rightarrow a$ and $B\rightarrow b$ to G. and then rewrite production $S \rightarrow aTbS$ as $S \rightarrow ATBS$

   Doing same for all production we will have production set of $G$ as follow:

   $S_0 \rightarrow S$

   $S \rightarrow ATBS|ABS|ATB|AB$

   $T \rightarrow ATB|AB$

   $A \rightarrow a$

   $B \rightarrow b$

5. Now we handle the case where RHS of production contains more than 2 non-terminals. What we do is simple. We just keep first non-terminal as it is and introduce new nonterminal for remaining part. Again example will make this clear.

   We have this $S \rightarrow ATBS$ production. So we introduce new non-terminal $C$ and add production $C\rightarrow TBS$. Then modify original production as $S\rightarrow AC$.

   Note here that now we have to do this process for newly introduced production also. i.e $C\rightarrow TBS$ will be converted to $C\rightarrow TD$ for instance and we have to add $D \rightarrow BS$

   Now after this step $G$ will contain following productions:

   $S_0 \rightarrow S$

   $S \rightarrow AC|AD|AE|AB$

   $C \rightarrow TD$

   $D \rightarrow BS$

   $E \rightarrow TB$

   $T \rightarrow AE|AB$

   $A \rightarrow a$

   $B \rightarrow b$

So now grammar is in CNF. But one thing is still remaining. Original grammar produces empty string but this grammar does not. For that add production $S_0 \rightarrow \epsilon$ to $G$.