9
$\begingroup$

I am trying to learn how to convert any context free grammar to Chomsky Normal Form. In the example below, I tried to apply Chomsky Normal Form logic, to result in a grammar, where every symbol either produces two symbols, or every symbol produces a terminal.

I am not %100 sure my implementation is correct, and it is important that I understand how to do this, I would appreciate if someone would let me know if I am on the right track.

Context Free Grammar

S -> ASA | aB
A -> B | S
B -> b | epsilon

After converting to:

Chomsky Normal Form

S-> CA | CB
C -> AS | a | S
B -> b | epsilon

Many Thanks in advance!

$\endgroup$
10
$\begingroup$

Conversion from Context Free Grammar to Chomsky Normal Form : (I ll tell you the steps and will also solve the example you asked simultaneously)

Step 1 : Introduce New Non-terminal $S_0$ and make it derive the start variable which is S

Thus

$S_0$ -> S

S -> ASA | aB

A -> B | S

B -> b | $\varepsilon$

Step 2 : Eliminate all $\varepsilon$ transitions

THus we need to eliminate B -> $\varepsilon$

For this we must to replace B with $\varepsilon$ in RHS of every production having B

THus we get,

$S_0$ -> S

S -> ASA | aB | a

A -> B | S | $\varepsilon$

B -> b

Now new $\varepsilon$ transition is introduced which is A -> $\varepsilon$ .. thus we need to eliminate it too

$S_0$ -> S

S -> ASA | aB | a | SA | AS | S ... Note: S -> S can be ignored

A -> B | S

B -> b

Step 3 : Eliminate all Unit transitions i.e. those productions having exactly one non-terminal in RHS .

thus we need to eliminate A -> B , A->S ,$S_0$ -> S

THus,first removing A-> B

$S_0$ -> S

S -> ASA | aB | a | SA | AS

A -> b | S

B -> b

NOw removing A-> S

$S_0$ -> S

S -> ASA | aB | a | SA | AS

A -> b | ASA | aB | a | SA | AS

B -> b

NOw removing $S_0$ -> S

$S_0$ -> ASA | aB | a | SA | AS

S -> ASA | aB | a | SA | AS

A -> b | ASA | aB | a | SA | AS

B -> b

Step 4 : Now eliminate all the productions that are non in CNF

$S_0$ -> AM | NB | a | SA | AS

S -> AM | NB | a | SA | AS

A -> b | AM | NB | a | SA | AS

B -> b

M -> SA

N-> a

The above CFG is in CNF .

:)

$\endgroup$
  • $\begingroup$ Thank you for the response, it seems very helpful, however, I am not sure why you added a terminal 'a' to your S symbol on step two, that did not appear in step 1, can you please explain? $\endgroup$ – AnchovyLegend Feb 6 '13 at 15:49
  • $\begingroup$ Substituting B=$\varepsilon$ in S-> aB produces S->a $\endgroup$ – Jay Teli Feb 6 '13 at 16:13
  • $\begingroup$ this is bcoz a$\varepsilon$ = a $\endgroup$ – Jay Teli Feb 6 '13 at 16:14
  • $\begingroup$ Thanks for the reply. Also, In step 3 part 1, how come symbol A produces terminal 'b'? and in step 3 part 2, how come A produces so many terminals? $\endgroup$ – AnchovyLegend Feb 6 '13 at 16:26
  • $\begingroup$ Step3 Grammar 1 ,Substituting all productions of B (which is B->b) gives us A->b .... This was done bcoz we wanted to eliminate A->B $\endgroup$ – Jay Teli Feb 6 '13 at 16:29

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