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.

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!

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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 .

:)

share|improve this answer
    
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? –  Epsilon Feb 6 '13 at 15:49
    
Substituting B=$\varepsilon$ in S-> aB produces S->a –  Jay Satish Teli Feb 6 '13 at 16:13
    
this is bcoz a$\varepsilon$ = a –  Jay Satish Teli Feb 6 '13 at 16:14
    
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? –  Epsilon Feb 6 '13 at 16:26
    
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 –  Jay Satish Teli Feb 6 '13 at 16:29

protected by Community Jun 7 at 0:32

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

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