chomsky-normal-form

Converting CFG to CNF,is it correct?


Given this CFG

 S->A|t|pCq
 S->B|r|^
 A->C|q|BA
 C->S|p|^
 B->m

My try to convert in CNF

Removing Null productions first i.e S->^ and C->^

So after removing

S->A|t|pCq
S->B|r
A->C|q|BA
C->S|p
B->m

Now removing unit productions i.e S->B, A->C, S->A and C->S

 S->B gives S->m using B->m

 A->C gives A->p using C->p

 S->A gives S->q|BA using  A->q|BA 

 C->S gives C->t|pCq|r using S->t|pCq

so adding these productions

S->t|pCq|q|BA

S->r|m

A->q|BA|p

C->p|t|pCq|r

where K->q,U->p

required CNG in CNF is

S->t|UCK|q|BA

S->r|m

A->K|BA|U

C->U|t|UCK|r    

R->UC

S->t|RK|q|BA

S->r|m

A->K|BA|U

C->U|t|RK|r

R->UC 

K->q

U->p

Is this one correct ?


Solution

    1. Removing the Null productions. Some definitions allow S to have a null production, you removed the C production incorrectly. You were supposed to create another production for each production which had a C in the RHS by replacing the C with null.

      S->A|t|pCq|pq
      S->B|r
      A->^|q|BA
      C->S|p
      B->m
      

      Note: After processing C->^, when you move to S->^, you do not add another C->^ production since that has already been processed. A->^ must be added however (A->C & C->^).

    2. Remove the A -> ^ production

      S->A|t|pCq|pq
      S->B|r
      A->B|q|BA
      C->S|p
      B->m
      
    3. Remove A->B and S->B

      A->m|q|BA
      S->A|m|t|r|pCq|pq
      
    4. Remove C->S

      C->A|p|m|t|r|pCq|pq
      

      Notice how A is also added since S->A hasn't been processed (easier to process it first, I'm just demonstrating a point)

    5. Remove C->A

      C->q|p|m|t|r|pCq|pq|BA
      
    6. Remove S->A

      S->q|m|t|r|pCq|pq|BA
      
    7. Final S->m|r|q|t|pCq|pq|BA A->m|q|BA C->m|p|q|t|r|pCq|pq|BA B->m

    8. Convert to CNF

      P->p
      Q->q
      X->CQ
      S->m|r|q|t|PX|PQ|BA
      A->m|q|BA
      C->m|p|q|t|r|PX|PQ|BA
      B->m
      

    Optional:

    S->^
    

    EDIT: Oops. I made a mistake. Forgot to add C->r. Sorry ^^'