Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
Actually, I'm also pretty sure that equivalence of CFGs is in fact not decidable. –  starflyer Sep 29 '11 at 23:59
    
@starflyer: Oops, horrible typo fixed. Thanks. –  Henning Makholm Sep 30 '11 at 0:16
add comment

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

$\quad S \to SS \mid a \mid b$

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.