# Converting CFG to CNF

I have the following problem of converting CFG to CNF:

\begin{aligned} S \Rightarrow\,& bA \mid aB\\ A \Rightarrow\,& bAA \mid as \mid a\\ B \Rightarrow\,& BB\mid bs\mid b \end{aligned} I know that Chomsky normal form only has productions of the type $A\Rightarrow BC$ and $A \Rightarrow a$. In the case of $A\Rightarrow bAA$, can I replace $b$ by $C_1$, i.e., $A\Rightarrow C_1AA$ and $C_1\Rightarrow b$?

Is this the right way to do it? Can some one guide me?

## 1 Answer

Hint:

Suppose we have $N \to PQR$. We replace it by two productions $N \to N_1R$ and $N_1 \to PQ$. If $N \to ab$, we take $N \to P_1P_2$, $P_1 \to a$ and $P_2 \to b$.

For example, let's consider $A \to bAA$ (it is, obviously, not in CNF). You could replace it by productions $A \to A_1A_2$, $A_1 \to b$, $A_2 \to AA$ (all in CNF), or you could use another set of productions.

• So i can write A⇒C1AA and A⇒C2A and C2⇒C1A Is this right? – techno Nov 25 '13 at 16:10
• Okay,Is there something wrong in what i have written C1 and C2 are non terminals – techno Nov 25 '13 at 16:16
• So you mean that it should not be replaced by the pair of productions? – techno Nov 25 '13 at 16:25