2
$\begingroup$

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

There are 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 got confused. I have now both C and F that go to AB. If I've done this correctly that would mean that either C or F can simply be removed. Or, of course, I've done something wrong in this procedure.

$\endgroup$
  • 1
    $\begingroup$ "I'm trying to prove that the following CFG can be converted to a CNF:" -- Every CFG can; it's called Chomsky Normal Form for a reason. Just follow the algorithm from that proof. $\endgroup$ – Raphael Sep 19 '16 at 19:43
6
$\begingroup$

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; the example 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 :-)

$\endgroup$
  • $\begingroup$ Thank you for the answer. Was both fun to read and very informatic. I cannot upvote it yet but i will as soon as i get enough points. Cheers! $\endgroup$ – Byfjunarn Sep 20 '16 at 9:08
0
$\begingroup$

1) no empty production 2) no unit production 3) convert all mix term and terminal greater than one into capital

S->AAB A->AAB/BB B->a A->a

4) Reduce the length of each non terminal upto 2 and add new rule S->TB A->TB/BB B->a A->a T->AA (new rule)

$\endgroup$
  • 1
    $\begingroup$ I don't see how this answers the question. A little explanation would make this answer much clearer. In particular, what does this answer add to the existing answer above? $\endgroup$ – Discrete lizard Feb 11 at 9:25

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.