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?
0
$\begingroup$
$\endgroup$
-
2$\begingroup$ Welcome to CS.SE! See en.wikipedia.org/wiki/Chomsky_normal_form and en.wikipedia.org/wiki/…. Which definition of CNF are you using? I encourage you to ask whoever told you that to explain why they said that, and summarize their argument here. $\endgroup$ – D.W.♦ Apr 4 '17 at 17:30
3
$\begingroup$
$\endgroup$
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".
-
$\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
