Construct the CNF for the following grammar and explain the steps. S→aAa | bBb |€, A→C|a, B→C|b, C→CDE | €, D→A|B|ab

Question

S→aAa | bBb |€, A→C|a , B→C|b , C→CDE | € , D→A|B|ab

In this i think E,C,D are useless but if we remove those, then there is no point in this question, so I'm stuck about what are useful and what are not and eventually how to convert it into CNF

Answer 1

Actually if we want to convert a grammar converted into a normal form then the grammar must be a context free grammar.

The context free grammar should satisfy the below conditions:

(i)€-Eliminations

(ii)Elimination of Unit productions

(iii)Elimination of useless symbols

According to this first we need to convert our grammar into Context-Free grammar The steps are:

Elimination of € productions:

step-1:

   S->aAa|bBb|€
   A->C|a|€
   B->C|b|€
   C->CDE
   D->A|B|ab

here C has € production so we replacing all the places of C with € and without €.

step-2:

   S->aAa|aa|bBb|bb|€
   A->C|a
   B->C|b
   C->CDE
   D->A|B|ab

here A,B has € productions so we replacing all the places of A,B with € and without €.

But S also producing € we can't remove € at S we need to conclude that output might also be a € since the starting symbol S as itself has € production.

Elimination of Useless symbols:

Step-1:

   S->aAa|aa|bBb|bb|€
   A->a
   B->b
   D->A|B|ab

we removed the C since if we want to expand the C it contains CDE in this there is no expansion for E. So we need to remove C.

Step-2:

   S->aAa|aa|bBb|bb|€
   A->a
   B->b

Here we removed the expansion of D since there no scope of reaching D.

In this there are no Unit productions

So finally the context free grammar is,

           S->aAa|aa|bBb|bb|€
           A->a
           B->b

Now we need to convert this into a CNF.

The conditions that are needed to satisfied by CNF are (i)X->x (ii)X->YZ where x is a terminal and X,Y,Z are Variables.

Now we need to add some more Variables C,D where

         C->Aa
         D->Bb

So our grammar will be look like this,

         S->AC|AA|BD|BB|€
         A->a
         B->b
         C->Aa
         D->Bb

we need to modify this some little.

         S->AC|AA|BD|BB|€
         A->a
         B->b
         C->AA
         D->BB

This is our CNF.