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?



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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.