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

Q5) Minimize (i.e. produce a minimal version) the following FSM clearly showing all the steps and procedure involved. 2 Marks for each step involved and 2 Marks for the final machine. 10 Marks a a a b 3 6 a a b 5 Q6) Design a Turing Machine that decides the following language over the alphabet {0, 1}. L = {0*10*1 |i, j>0} You need to clearly describe the language (1 Mark) showing the sample valid and invalid strings, describe the logic followed for the construction (2 Marks), write the acceptance and rejection conditions (1 Mark). You get 6 Marks for the final correct machine. 10 Marks