Question

Theory of computations

An Introduction to formal language and automata 6th edition.

Chapter 6: Simplification of context free grammars and normal forms.

Solve the following questions.

Please solve it clearly

1. Do Exercise 4 of Section 6.2 at page 176. 4. Transform the grammar with productions S baAB A bABIA, B BAa IAIA into Chomsky normal form.

use Keyboard not hand writtin answers.

Thank you.

Answer 1

A Contest-Free- Grammer(CFG) is in Chomsky Normal Form(CNF) if the productions are in the form:

S-> $\epsilon$ /AB

A -> BC

A->a

Where S(Start symbol),A,B,C are non terminals, and a is the terminal.

First of all, we should find out whether the start symbol(S) is in right hand side of productin are not.

Here there is no si in righ hand side production.

Start with S->baAB

Now b is replaced with M, then production is S->MaAB, M->b

Now a is replaced with X, then production is S->MXAB,M->b,X->a,

Now XAB is replaced with P, then,S->MP,M->b,P->XAB,X->a,

Now AB is replaced with L, then, S->MP,M->b,P->XL,X->a,L->AB,

Now come to second production A ->bAB| $\lambda$

Replace AB with L(since L->AB from above), and replace b with M, then

A->ML| $\lambda$ , M->b,L->AB,

Now come to third production B->BAa|A| $\lambda$

Replace BA with K and a with X, then

B->KX|A| $\lambda$ , K->BA,X->a

Now check with Chormsky Normal form rules,

productions are now in Chomsky Normal Form(CNF)