0
$\begingroup$

I thought that, for every CFG, there is an equivalent grammar in CNF. I was told this is false. Can someone explain to me why this is false and possibly provide a counter example?

$\endgroup$
3
$\begingroup$

Depends on how strict you interpret "equivalent". A CFG in ChNF cannot generate the empty string. If you want to have a more precise statement:

For every CFG $G$ there is a grammar $G'$ in ChNF such that $L(G) = L(G') - \{\varepsilon\}$.

So now we have two choices.

Either to accept the loss of the empty string, which in practise is not a big deal. Or we have to adapt the definition to make room for generating the empty string in a special way. This usually means we allow a production $S\to \varepsilon$ where $S$ is the axiom, provided $S$ does not occur as right hand side of productions.

This is a matter of taste: there is no "best" definition. Personally I think having a special production for $\varepsilon$ is not elegant, and prefer a notion of equivalence "upto the empty string".

$\endgroup$
  • $\begingroup$ Some definitions of CNF include $S \to \varepsilon$ (and $S$ can't appear on any right-hand-sides) for specifically this purpose. $\endgroup$ – Raphael Apr 4 '17 at 18:52
  • $\begingroup$ You are right of course. Thanks. I consider that a quick hack, for people that do not want to lose the empty word. $\endgroup$ – Hendrik Jan Apr 4 '17 at 18:58
  • $\begingroup$ It sure is! I think this here is a nice opportunity for learners to gain some intuition about which aspects of a model "matter". $\endgroup$ – Raphael Apr 4 '17 at 19:00
  • $\begingroup$ Thanks, this helps clear up my question. Is there debate on the exact definition of CNF as to whether or not it should/can include the empty string? $\endgroup$ – MoreFoam Apr 5 '17 at 19: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.