Marking Scheme and Common Errors, Q2 & Q4 Test 1
Tim Paterson

Q2: 
10 Marks for the correct DFA
1 per minor error (transition incorrect, state incorrect)

If the DFA was incorrect at a fundamental level, but showed good work
from that point on, I gave the student 5 marks (-1 for minor errors in
work, as above)

Q4: 10 marks for a complete solution.  Part marks as follows:
2 marks for correctly stating the M-N Theorem
4 marks for correctly identifying a set of equivalence classes
4 marks for showing that these equivalence classes were pairwise
distinguishable, and stating that therefore the language was not
regular.

Q2:  This was generally well done, although many students made the
error of thinking delta({q_0, q_1}, a) = {q_0, q_2} rather than {q_0,
q_1, q_2}. 

Q4: This question was done quite poorly.   Most students made one of
the following mistakes:

1) Stating that regular languages have to be finite, and concluding
that A is not regular because it is infinite

2) Mistaking the M-N theorem for a statement about distinguishability
(i.e. that A is regular if it contains two strings that can be
distinguished), or a statement about equivalence relations (some
students attempted to show that the language A was an equivalence
relation either with itself, or with Sigma-*.

3) Some students attempted to show that A was not regular using some
other method (usually by arguing that it couldn't be represented by a
finite set of states).  However, they didn't do this in the context of
the M-N Theorem (i.e. by using the equivalence classes of the
language).