# For every context-free grammar, is there an equivalent grammar in Chomsky normal form?

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?

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".

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