Instructions:

* Answer all questions.

*Though the questions sound abstract in some cases due to the nature of the module, you are required to clearly describe the steps involved in producing the final solution, which means your solution should be comprehensive. Simply showing the final solution will attract heavy penalty.

*Each question carries 10 Marks.

Q1) Describe in words the language generated by the following grammar. 2 Marks

What abstract machine is appropriate to recognize this grammar? Why? 1 Mark

Construct the machine. 4 Marks

Verify whether it recognizes the language you described. 3 Marks

(i.e., you need to show how a valid string is recognized and an invalid string is rejected by the machine.)

S | aS | bA | cD

A | cD

D dA

Q2) Describe in words the language generated by the following grammar. 2 Marks

What abstract machine is appropriate to recognize this grammar? Why? 1 Mark

Construct the machine. 4 Marks

Verify whether your machine recognizes the language you described. 3 Marks

(i.e., you need to show how a valid string is recognized and an invalid string is rejected by the machine.)

S aAb

A | c | aBb

B aCb

C A