Question

5. (10 points) Convert the following grammar G over Σ-{a, b} into Chomsky normal form. Note that G already satisfies the conditions on the start symbol S, A-rules, useless symbols, and chain rules. Show your steps clearly.

Answer 1

1. Add anew start symbol S0.

Hence grammar becomes

S0->S

S->bT

T->aAA|AbAT

A->aT|bT|a

2.no null productions and no unit productions are there . Hence skip to next step by removing unit production S0->S

3.Remove terminals on right side that exists with non terminals.

S0->S

S->YT

T->XAA|AYAT

A->XT|YT|a

X-> a

Y-> b

4.Reduce productions that has more than 2 non terminals. In this case T->XAA and T->AYAT

Hence reduced form can be given by:

S0->S

S->YT

T->XZ|AL

A->XT|YT|a

X-> a

Y-> b

Z-> AA

L->YM

M->AT