Here is a marking scheme and comments for Q3-6
(Tim Paterson)

Q3

10 marks for the right answer.
-1 per minor mistake
-2 per serious mistake

In particular, -2 marks if you didn't take into account "negative
accounting" of your stack symbol.  That is to say, if you were pushing
two zeros for every 1 and popping a zero for every 0, you would lose
two marks for not considering the case where many 0's occur before any
1's.

Q4

10 marks for correctly applying the pumping lemma
-1 mark for each minor missed case
-2 marks for each serious missed case (such as v=a^m y=b^m where you
need to pump down)
-5 marks for (incorrectly) assuming that you can select the contents
of v, x, and y.

Q5

3 marks for showing that all CFLs can be accepted by some 2PDA
3 marks for presenting a non-CFL that some 2PDA accepts
4 marks for demonstrating that a 2PDA accepts that language

Q6 (Bonus)

2 marks for stating that the grammar must be converted to CNF
3 marks for presenting a correct algorithm

Comments
=======

Q3

This was generally well done, except that almost everyone made the
mistake of not taking into account the 'negative accounting' mentioned
above.

Q4

This question was generally done quite poorly.   Most students missed
at least one important case.  Quite a lot of people made the mistake
of trying to choose the contents of v and y.

Q5

This question was very well done and almost all students correctly
identified a suitable non-CFL and gave an algorithm for a 2PDA which
accepts that language.  The most common mistake was forgetting to show
the other direction (i.e. that all CFLs could be accepted by 2PDAs).

Q6 (Bonus)

Answers to this question were good, although many students lost marks
for not stating that the grammar should be converted to CNF first.
Algorithms for testing membership in non-CNF grammars tend to have
problems halting when confronted by loops of unit rules, and in
situations where many variables can generate epsilon.