Marking Schemes for Question 1 & 2: (Liuxing Kan) Question 1: If your CFG can generate some but not all strings in that language, you get 5 marks. If you CFG is completely right, you will get 10 marks. If you don't give a CFG, you will get 0 marks. Question 2: Part a), If you just give a explanation, you will get 1 marks. If you give two different parse trees or two different derivations, you will get 3 marks. Part b), If you don't use induction on the length of derivation, but with a clear description, you will get 5 marks. If your induction has some problems(e.g. the base case is wrong, etc), you will get 5 marks. Those who have complete proofs by induction will get 7 marks. Comments: A lot of student didn't give the right answer in Q1, because they ignore string "a...a", "b...b" and "c...c" are in that language. Also, there are some students who give a PDA not grammar. Please read the question carefully next time. In part a of Q2, nearly all students are right. And in part b, only giving description is not enough, you should give formal proof by induction. Some students ignore it.