# Converting to Chomsky normal form

Im having some problems with a qeuestion regarding converting a context free grammar to chomsky normal form.

I have S -> abC | babS | de C -> aCa |b

I know what to do with the case of aCa and de and b but im not sure how to handle the abC case or the babS case. I believe that chomsky normal form is supposed to have outputs of only 2 characters. so with something like aCa you make and output aa and have A->a and create another nonterminal? X -> SA but I dont know how im supposed to handle the abC case or the babS case.

• What research have you done? Have you studied how to convert a grammar to Chomsky to normal form? It sounds like not. So, I suggest you read up on this in Wikipedia or in your textbook.... – D.W. Nov 25 '13 at 3:41
• I recommend that you read about how to convert a grammar into Chomsky normal form. There are standard techniques for doing so. For instance, they're most likely covered in your textbook. Wikipedia also explains a procedure for converting any grammar to Chomsky normal form. That should be sufficient to help you solve your exercise on your own. – D.W. Nov 25 '13 at 3:42

## 1 Answer

Let's work it out through the conversion algorithm given in Wikipedia.

input:
$S \to abC \mid babS \mid de$
$C\to aCa \mid b$

1. Introduce $S_0$:
$S_0 \to S$
$S \to abC \mid babS \mid de$
$C\to aCa \mid b$
2. remove $\epsilon$ rules: there are no $\epsilon$ rules, so nothing changes.
3. eliminate unit rules: Originally, there are none, but we added one, namely $S_0\to S$. Since it's the only one, we'll deal with it later (after $S$ is already in CNF). This will be done by adding, for any rule $S\to V_iV_j$, the rule $S_0 \to V_iV_j$. But let's first complete the conversion.
4. replace all other rules into normal form: we take each transition which is not in the correct form and replace it with $N\to V_iV_j$, introducing new non-terminals $V_1, V_2,...$ as needed:
• $S\to ab C$ $\Longrightarrow$ $S\to V_1 C$ setting $V_1 \to ab$. The new $V_1$ is not in CNF, but can easily be converted to CNF by re-defining it as $V_1\to AB$ with $A\to a$, $B\to b$.
• $S\to babS$ $\Longrightarrow$ $S\to V_2S$ adding $V_2 \to bab$. Now $V_2$ is not in CNF, so we change it to $V_2 \to V_3B$ adding $V_3\to BA$. (skipping a trivial step here)
• $S\to de$ is almost CNF. We change it to $S\to DE$ and add $E\to e$, and $D\to d$.
• $C\to aCa$ $\Longrightarrow$ $C\to AV_4$ where $V_4 \to CA$.
• $C \to b$ is already in CNF.

so we end up with:
$S_0 \to S$
$S\to V_1 C$
$S\to V_2S$
$S\to DE$
$C\to AV_4$
$C \to b$
$V_1 \to AB$
$V_2 \to V_3B$
$V_3 \to BA$
$V_4 \to CA$
and $A\to a$, $B\to b$, $D\to d$, $E\to e$.

Finally, we need to deal with the unit rule $S_0 \to S$. As said, we will replace the $S$ in the right-hand-side with the "content" of S. That is, we remove that unit rule and add instead:
$S_0 \to V_1C \mid V_2S \mid DE$.