Raghunath Tiwari(NPTEL NOC Chomsky Normal Form)

Question

S->ASB

A->aASA | a | ϵ

B->SbS | A | bb

Convert this grammar into Chomsky Normal Form

Comments

I think there is a problem with the question because S given in the grammar is nonterminating ,since it has no terminating productions. Please check the question.

Answer 1

We can do by eliminating epsilon and unit productions in the given grammar,

First eliminate and write the grammar accordingly as CNF,

S → AU2|SB|AS

A → V1U3|a|V1S

B → SU4|V2V2|V1U5|a|V1S

U1 → SB

U2 → SB

U3 → AS

U4 → V2S

U5 → AS

V1 → a

V2 → b

Please correct me if iam wrong

Comments

thanks!!

but "B" contain null production.

---

Same you have to again remove from B

---

thanks!!!