The following are marking schemes I used for question 1,2,3: Marking Schemes For Test 2: Question 1: If your regular expression can generate at least one string satisfied the language, you will get 5 marks. And if you give an exact solution can generate all these strings satisfied the language, you will get full marks. Remarks: All students got at least 5 marks in this question, and most of them get full marks. Question 2: Part A: If you give a regular expression can generate at least one string satisfied the DFA, you will get 1 mark. And if you give an exact solution, you will get 5 marks. Part B: If you give a description about how to compute R(0), you will get 1 mark. If you give a description about how to compute R(k), you will get 2 marks. The rest 2 marks is for showing that how to obtain R. Remarks: Part A is not difficult. Some students failed to give an exact solution because they didn't inspect and think carefully. Part B is done well. Everyone knows how to use induction to obtain R. If you didn't get full marks, maybe that because you didn't give briefly descriptions or explain clearly. Question 3: Part A: If you give an exact solution, you will get 5 points. If you know what pumping lemma is but fail to give a proper proof, you will get 2 points. Part B: If you give an exact solution, you will get 5 points. If you have some basic ideas, but don't show proof clearly, you will get 3 points. If give the solution for 0 power of (2*n) not for 0 power of (2 power of n), you will get 0 point. Remarks: Part A is done very well. Many students know the basic ideas about part B, but failed to show proof clearly, while some of them give the very clear proof. Also, there are some students who didn't check the part B carefully. That is 2 power of n while is not 2*n. It's pity to make such kind of mistake. Liuxing