If you want to make money online : Register now

[Solved]: Converting CFG to CNF (context-free grammar to chomsky normal form)

, , No Comments
Problem Detail: 

I'm trying to prove that the following CFG can be converted to a CNF:

S->aAB

A->aAa

A->bb

B->a

Here below is how i've managed so far:

Step 1: add a new start state:

S0->S

S->aAB

A->aAa

A->bb

B->a

Step 2: remove epsilon rules (No such rules in this CFG)

Step 3: remove non-terminal to non-terminal rules

S0->aAB

S->aAB

A->aAa

A->bb

B->a

Step 4: make right-hand-side not contain more than 2 non terminals OR 1 terminal:

S0->BC

S->BC

A->BF | EE (A->aAa and A->bb in one line)

B->a

C->AB

E->b

F->AB

So this is where i get confused... I've now got C and F that are both ->AB. If i've done correct that would mean that either C or F can simply be removed. Or of course i've done something wrong in this proof. Hopefully someone here on stackexchange can shed some light in the matter.

/Byf

Asked By : Byfjunarn

Answered By : reinierpost

You're right to be cautious, but there is nothing wrong.

A context-free grammar is in Chomsky Normal Form if and only if every rule is of the form:

A → BC,  or A → a,   or S → ε,   where S is the start symbol. 

Consider the grammar

S → TU S → UT T → a U → a 

Is this a valid context-free grammar in Chomsky Normal Form?

Yes, it is. Each rule is of one of the allowed forms.

But - you say - T and U have the exact same rules; one can be replaced with the other!

Congratulations: you have invented a normal form! A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides.

This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it.

But the algorithm you're using to bring arbitrary grammars into Chomsky Normal Form doesn't. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; my example above proves it. Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form. But nobody asked it to. Except you.

Just let the poor algorithm go about its ways. You know what to do once it's finished :-)

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/63646

 Ask a Question

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback