[Math] Chomsky Normal Form Questions

context-free-grammarformal-languages

First question is, is the Chomsky Normal Form grammar unique for a given grammar G? So this is sort of a strawman question as I'm pretty sure it's not unique.

If so, then what does the normal mean?

Best Answer

It's clear that Chomsky normal form grammars are not unique. If they were, we could check two grammars for equivalence by transforming them to normal form and see if they were equal -- but equivalence of context-free grammars is known to be undecidable.

The phrase "normal form" is a bit fuzzy; there are no properties that are required to use it. You get whatever you get, in each case.

In the case of Chomsky normal form, the relevant sense of "normal form" is something like "a restricted form that is nevertheless strong enough to express everything we're interested in".

One use for such a normal form could be to simplify proofs. If you're trying to prove that something or other holds for all context-free languages, it may be technically simpler to assume that the grammar is given in Chomsky normal form than it would be to treat arbitrary context-free grammars. For example, induction steps may be easier to carry out if you can assume there are no inner $\epsilon$-productions.