Question

1. [10 Points Convert the following grammars into Chomsky Normal Form. (a) S → AaB | BAC A AaB | BA B → ABaC BACC C → Cb CaА | 6C (b) S XSX a Ab | bAa A + XAXX X + ab

Answer 1

a)answer)

S->AaB becomes

S->WB

W->AX

X->a

S->BAaC becomes

S->UV

U->BA

V->XC

A->AaB becomes

A->WB

W->AX

X->a

A->BAb BECOMES

A->KZ

K->BA

Z->b

B->A becomes

B->LA

L->λ

B->BaC becomes

B->BM

M->XC

B->BAC Becomes

B->BN

N->AC

B->C BECOMES

B->LC

L->λ

C->Cb becomes

C->CY

Y->b

C->CaA becomes

C->CO

O->XA

C->bC BECOMES

C->YC

Y->b

ANSWER)

a)answer)

S->WB

W->AX

X->a

S->UV

U->BA

V->XC

A->WB

W->AX

X->a

A->KZ

K->BA

Z->b

B->LA

L->λ

A->λ

B->BM

M->XC

B->BN

N->AC

B->LC

L->λ

C->CY

C->CO

O->XA

C->YC

B)ANSWER)

S->XSX becomes

S->XY

Y->SX

S->aAb becomes

S->MN

M->a

N->AL

L->b

S->bAa becomes

S->LP

P->AM

A->XAX becomes

A->XO

O->AX

A->X becomes

A->EX

E->λ

A->λ becomes A->λ

X->a becomes X->a

X->b becomes X->b

answer)

S->XY

Y->SX

S->MN

M->a

N->AL

L->b

S->LP

P->AM

A->XO

O->AX

A->EX

E->λ

A->λ

X->a

X->b