Converting CFG to CNF,is it correct?

Question

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 ?

Answer 1

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 ^^'