Marking Scheme for question 1 & 2: Q1: 1 If you just give a transition function without description, you only get 5 marks 2 If your description is not complete, you will get 8 or 9 marks depended on your explanations. 3 If you just decide this language by using 0s-1s counters, but didn't show how to keep the counters in TM, you will get 7 marks. Remarks: This question is done quite well. Nearly all students know the basic ideas. But some didn't get a clear and complete description about this turing machine. Q2: 1 If you show this language precisely, you will get 5 marks. If your language is not exactly right, but it can generate some strings which can accept by this turing machine, you will get 2 marks. 2 If you give a proper induction proof, you will get 5 marks. (2 marks for the base case and 3 marks for the induction step.) Remarks: This question isnt done very well. Only a few of students get the right answers of this language. I think its because they didnt analyze in a proper way. They should know more details in how to construct a TM by a language and how to give a language by a TM. Hopefully they can get good marks in final.