\begin{align*} S&\to AACD\\ A&\to aAb\\ C&\to aC\mid a\\ D&\to aDa\mid bdb\mid\varepsilon \end{align*}

I think that this grammar is infinite so it is not possible to convert it into cnf. Am I correct ?


1 Answer 1


Every context-free grammar can be converted to Chomsky normal form. Also, note that grammars are by definition finite: a grammar might describe infinitely many strings, but the grammar itself is finite.

  • $\begingroup$ What will be it's cnf form ? $\endgroup$ Commented Dec 5, 2018 at 20:08
  • 1
    $\begingroup$ All the standard references explain how to convert a grammar to CNF. $\endgroup$ Commented Dec 5, 2018 at 20:12
  • $\begingroup$ S is not terminating. That's what the confusion is. I'm unable to convert it. $\endgroup$ Commented Dec 5, 2018 at 20:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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