Question

Need help with Theory of Computation.

Grade: Name: CSCI 4333 Theory of Computation Final December 4th, 2019 Part I. Short answer/problems. Answer all questions. Long rambling answer will be marked as incorrect Point values in parenthsis. 1. Given the following context free grammar over alphabet (a,b): S -> ABa A -> aab | BI B -> Ab | aa a. (6) Show that the grammar is ambiguous for a non-empty string b. (10) Convert the CFG to Chomsky normal Form.

i think ^ is an epsilon.

Answer 1

a)answer)

a grammar is ambiguous when at least one string of the language contain more than one left or right most derivation or two parse trees exist.

string =aaba

Leftmost derivation 1:

S->ABa

=aabBa

=aaba

Leftmost derivation 2:

S->ABa

=Ba

=Aba

=Bba

=aaba

string aaba there exist two leftmost derivations. so this grammar is ambiguous.

b)answer)

S->ABa becomes

S->XY

Y->a

X->AB

A->aab becomes

A->XZ

Z->XW

W->b

A->B becomes

A->EB

E->^

A->^ is same

B->Ab becomes

B->AW

B->aa becomes

B->YY

B->^ is same

finally CNF grammar is :

S->XY

Y->a

X->AB

A->XZ

Z->XW

W->b

A->EB

E->^

A->^

B->AW

B->YY

B->^