1 Use the algorithm given in class and in our textbook that

1. Use the algorithm given in class and in our textbook that takes a CFG and converts it into a CNF grammar that accepts the same language as the original grammar, except possibly for the string , to answer the following question. As part of your answer, you should say which variables are nullable, and you should give the appropriate grammar after each step of the algorithm.

Give a CFG in CNF that accepts the same language, except possibly for the string , as the following grammar:
S AB
A aA | b
B bBb | aa |

Solution

given CFG is

S -> AB

A->aA | b

B -> bBb | aa | ^

here the following steps are to be follow to convert the given CFG to CNF

1) Unit productions are to be removed from the given grammar. Hence A->b and B-> aa are removed

S-> AB | bB | Aaa | baa

A->aA

B-> bBb | ^

2) Now we will find out more than two variables in R.H.S

B->bBb

S->Aaa | baa

which are reduced to

B->bX and X->Bb

S-> AY | bY and Y-> aa

result grammar is

S->AB | AY | bY |bB

A->aA

B-> bX | ^

3) Here S-> bB , A-> aA are to reduced

S->AB | AY | bY | YB

A-> ZA

B-> bX | ^

the given grammar is in CNF converted from CFG