Here is my marking scheme for questions 4 and 5, along with some comments. Q4 == This was generally well done. Some people made some minor mistakes in the completion of the table. Others used the state minimization algorithm, rather than the Table Filling algorithm. Marking: 2 marks for the correct answer, 8 marks for a completely correct table. -1 mark per mistake in the table, -2 marks for using the state minimization algorithm. Q5 == This question caused some problems. The most common mistakes were: a) trying to show that the language of the DFA contained strings of length=7, rather than 7 strings in total (of all lengths) b) producing an algorithm that attempted to design a specific DFA that accepted only 7 strings, rather than an algorithm that works for all DFAs c) producing an algorithm that was basically correct, but didn't halt. Marking: 10 marks for the correct answer. 5 marks for correctly determining that the language wasn't infinite (by testing strings in the range n <= |w| <= 2n). 5 marks for correctly determining that, if finite, the language accepted exactly 7 strings (by testing strings in the range 0 < |w| < n) -1 to -4 marks for mistakes in each of these two halves, depending on severity. Not halting was counted as a fairly severe mistake, but marks were only deducted once.