Mumbai University > Computer Engineering > Sem 4 > Theoretical Computer Science

Marks: 10M

Year: Dec 2016

Observe that the CFG is in CNF. If we rename S as A1 and A as A2 respectively, the production will be then

A1->A2A2|a

and A2=A1A1|b

We leave A2->b, as it is in the required form.

Now consider A2->A1A1. To convert this we will use lemma to get

A2->A2A2|a

A2->aA1

i.e. by replacing the first A1 on RHS of A2->A1A1 by definition of A1. Now the production A2->aA1 is in required form. But we need to use Lemma for A2->A2A2A1 as it is of form A->Aα

Apply lemma to the productions of A2. A2 productions are

A2->A2 A2 A1

A2->aA1

A2->b

Here, β1=aA1, β2=b, α=A2A1

So we have now by adding new non-terminal Z2.

A2=aA1|b

A2->aA1 Z2|bZ2

Z2->A2A1

Z2->A2A1Z2

Now all A2 productions are in required form.

Now we will have to consider the A1, production,

A1->A2A2|a

Out of these A1->a is in required form.

So consider, A1->A2A2

Applying Lemma we get

A1->aA1A2|bA2|aA1Z2A2|bZ2A2