2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Actually, I'm also pretty sure that equivalence of CFGs is in fact not decidable. $\endgroup$ – starflyer Sep 29 '11 at 23:59
  • $\begingroup$ @starflyer: Oops, horrible typo fixed. Thanks. $\endgroup$ – Henning Makholm Sep 30 '11 at 0:16
2
$\begingroup$

A language's grammar in Chomsky normal form (CNF) is not uniquely defined, see for example

$\quad\begin{align*} S &\to AA \\ A &\to a \mid b\end{align*}$

and

$\quad S \to AB \mid BA$

$\quad A \to a$

$\quad B \to b$

Note that both grammars are reduced, every rule and symbol can be reached from the start symbol and every nonterminal can be derived to a terminal string.

I am not sure what the answer is if you asked for minimal grammars in CNF. If they are unique they can not be found algorithmically, as Henning points out.

As for the term normal, it just means that you have some guarantee regarding the form of some object. This may ($2-$conjunctive normal form of logics) or may not (CNF of grammars) have an impact on the represented space.

This guarantee is usually chosen such that it pays off somehow. In the case of CNF, its existence for any context free language simplifies some proves (e.g. Pumping Lemma) and algorithms (e.g. CYK).

There are typically several normal forms for one and the same type of object, each with their own benefits. Consider CNF vs Greibach normal form for context free grammars or con- and disjunctive normal forms of formulae of propositional logics.

$\endgroup$
  • $\begingroup$ These grammars are not equivalent, right? The second one only generates ab and ba, while the first one generates a, b, aa, ab, ba, bb, aaa, ... $\endgroup$ – Tempestas Ludi May 23 '17 at 8:09
  • 1
    $\begingroup$ @TempestasLudi Haha, my bad! To think that nobody noticed for over five years... Editing, thanks! $\endgroup$ – Raphael May 28 '17 at 16:40

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.