=========================================================================== CSC 236 Homework Assignment 3 -- Marking Scheme Fall 2009 =========================================================================== NOTE TO STUDENTS: You will find below the marking scheme used for your homework, including the meaning of marking codes and number of marks associated with each one. This file also contains my instructions to the marker (so you can get an idea of how the homework was marked) and the marker's comments about each question. Please take the time to read this carefully before you ask questions about the grading of your homework. NOTE TO MARKER: Be picky! On any homework, it is the responsibility of students to show that they understand how to solve each problem and to write up their answers carefully. At the same time, be on the lookout for reasonable misinterpretations of the question and mark leniently when the solution is correct based on some reasonable implicit assumptions -- of course, this is open to your judgement about what is "reasonable", but that is one area where you should be more lenient. Also, remember that marking is not just about evaluating the students's performances, but also about giving them feedback so that they can learn from their mistakes. This is especially important for students who made numerous or more serious mistakes, as they are likely to need more feedback in order to understand why their answers were incorrect. For each question, I list solution elements with an associated code for writing on student papers (the letter(s) between underscores _) and a number of marks. There are also general errors (with associated codes) given below, with a maximum number of marks to take off for each type of general error (as a percentage of the value of the question). You will likely encounter other common errors, or maybe decide to break down the marking scheme further. Simply make note of these changes/additions to the marking scheme, and introduce new code letters (or short words) to allow you to quickly give accurate feedback to the students (both in terms of what they did wrong and how many marks it cost them). For solutions that are significantly different from the expected, just use the following basic general breakdown of marks: _F_ormat [roughly 20%]: proper format/structure for the answer, independently of the solution's correctness _I_dea [roughly 40%]: correct high-level idea/intuition for the answer, independently of the format or details provided _D_etails [roughly 40%]: each part of the solution is provided and correct, independently of the format GENERAL ERRORS (marked negatively, in addition to any other errors): _N_otation [up to 20%]: incorrect/ambiguous notation _V_agueness [up to 20%]: incorrect/unjustified/vague claim 1. [20 marks] (a) [10 marks] _F_ormat [2 marks]: clear attempt to give an explicit FSA and a state invariant for it -- independently of the correctness _A_utomaton [4 marks]: correct FSA A_1 (accepts all strings in the language and none others) -- even if poorly justified _J_ustification [4 marks]: correct state invariant for A_1 (b) [10 marks] _F_ormat [2 marks]: clear attempt to give an explicit RE and justify its correctness (either directly or by showing the steps in a construction) -- independently of correctness _E_xpression [4 marks]: correct RE R_1 (describes all strings in the language and none others) -- even if poorly justified _J_ustification [4 marks]: good justification: either good high-level argument that L(R_1) = L_1 or clear indication of the steps in the construction of R_1 from A_1 Marker's Comments / Error Codes / Common Errors: For part (b), if there was an attempt at a state reduction but there was a mistake and the final RE was wrong, the score was usually 4. Giving a RE without any justification was usually a 2. 2. [20 marks] _F_ormat [4 marks]: clear attempt to give an explicit RE R_2 and to prove its correctness by showing double-inclusion (that L(R_2) subset of L_2 and that L_2 subset of L(R_2)) -- independently of correctness _E_xpression [6 marks]: correct RE R_2 (i.e., L(R_2) = L_2) -- even if not proved correct take off up to 2 marks for RE's that are much longer or more complicated than necessary _P_roof [10 marks]: good proof of correctness for R_2 (5 marks for each direction of the proof) Marker's Comments / Error Codes / Common Errors: - The two directions of the proof were graded separately (5 points for each). - If the proof for a direction was not convincing (i.e., had serious errors), I took off 4 or 3 points. - If the proof for a direction was unnecessarily long, I took off 1 or 2 points. - A common mistake was to say something like: "Since s does not have three consecutive zeros, and t does not have three consecutive zeros, we conclude that s.t does not contain three zeros." This is not correct because hypothetically, s could end with two zeros and t could start with a zero. Hence, neither s nor t would have three consecutive zeros, but s.t would. I took off 1 or 2 points for this. 3. [20 marks] _F_ormat [4 marks]: clear attempt to give an explicit FSA A_3 and to prove its correctness by stating and proving a state invariant, then using the state invariant to conclude L(A_3) = L_3 -- independently of correctness _A_utomaton [6 marks]: correct FSA A_3 (i.e., L(A_3) = L_3) -- even if not proved correct take off up to 2 marks for FSA's that are much larger or more complicated than necessary _P_roof [10 marks]: good proof of correctness for A_3 _I_nvariant [2 marks]: clearly stated and correct state invariant _S_tructure [4 marks]: correct inductive structure, including correct value for the base case, clear and correct statement of the inductive hypothesis, and correct breakdown of the inductive step into cases and sub-cases _C_ontent [4 marks]: correct proofs of each case Marker's Comments / Error Codes / Common Errors: E1 (-3/-2): You have not explained why, when you are in the state "q<" or "q>", seeing a [1 0] or [0 1] does not change the relationship between the first and second rows. Some people wrote out a mathematical expression to prove this, others just mentioned that once there is a difference in the more significant bits, nothing in the least significant bit can have an effect. I was not picky here, but this error code means that you did not explicitly address the issue. E2 (-1): You present the base case before stating what you are trying to prove or what you are inducting on or what you plan to show by the base case. E3 (-1): You have not shown why the state invariant implies that L_3 = L(A_3). [Instructor's Comment: Note that the marking scheme was very generous about this -- in a sense, this is the most important part of the proof.] E4 (-2): Your proof is unnecessarily long. This was often due to too many subcases that could have easily been combined. 4. [10 marks] (a) [10 marks] _F_ormat [2 marks]: clear attempt to give a proof by contradiction, and to obtain a contradiction by showing that some portion of a string can be repeated to obtain another string not in the language -- independently of correctness _I_deas [4 marks]: correct high-level idea of the proof -- even if some details are vague or missing _D_etails [4 marks]: proof is well-written and complete (b) [5 BONUS marks] _G_rammar [2 marks]: correct CFG G_4 _J_ustification [3 marks]: good argument that L(G_4) = L_4 Marker's Comments / Error Codes / Common Errors: E1 (-2): For the justification of part b, you had to prove two things: L(G_4) is a subset of L_4, and L_4 is a subset of L(G_4). You did not do this. Most people that applied the pumping lemma for part (a) did not do it correctly. In order to prove L_4 is irregular using the pumping lemma, you can pretend that you have an adversary and do the following: 1) The adversary picks any k he wishes. 2) Based on this k, you pick a string s that is in L_4. 3) The adversary then picks u, v, and w, as he wishes, as long as s = u.v.w, v is non-empty, and |uv| < k. 4) Now you pick any natural number i that you wish, and show that u.v^i.w is not in L_4. A common mistake was to try to define u, v, and w. You cannot do this -- whatever you prove in step 4 has to hold for all u, v, w as long as they satisfy the conditions of step 3.