Converting to Chomsky Normal Form

Question

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!

Answer 1

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 .

:)