0
$\begingroup$

\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 ?

$\endgroup$
2
$\begingroup$

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.

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

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.