Tiêu đề 0. Sample Marking Scheme CSE331 Midterm ✅

Set A (a) A correct DFA is worth the full 3 points. If the student misses one of the accepting states (with everything else being correct), award up to 2 points. Anything unsalvageably wrong is worth 0 points. (b)
- A correct DFA is worth 3 points - If the student misses one of the accepting states, award up to 2.5 points (with everything else being correct) - If the student tries something involving two states to keep track of whether or not they are at an even position, award up to 1.5 points. (c) The answer is 3*3=9. The student does not have to arrive at the correct answer. She only has to demonstrate the knowledge that you have to multiply the state counts. In other words, award her the full 1 point if the student has m states in her DFA for Problem (a), n states in her DFA for Problem (b), and has m*n as her answer in (c). (d) The strings are 00000 and 00001. 0.5 points for each correct string listed. (e) - A correct DFA is worth 2 points. - With everything else being correct, deduct 0.5 points if the student does not mark the start state as an accepting state. - Any attempt at determining the parity of which index you’re on using two states should be worth at least 0.5 points.
(a) Possible correct answers include the following: - Award the full 2 points if the student has anything equivalent to the answers above. - Deduct 0.5 points if the student misses the (1 \cup \varepsilon) from the first two answers. These are small corner cases. - Award at least 0.5 points if the student’s answer does not match any string in L_1’. It is possible that his answer misses some subset in L_1. Depending on the nature of these subsets, this 0.5 can become a 1.5 (see, for example, the last point). Grade at your discretion. - Award 0 points, if the student’s answer matches any infinite subset of L_1’. (b) Any five-letter string of the form (0|10)*1 is correct and worth the full 2 points. An incorrect answer is worth nothing. (c) The answer is anything equivalent to (0|10)*1. No points for partial progress Anything equivalent to (0*10*1)*0* is worth the full 2 points. - If the student’s answer does not match the strings of the form 00...0000, then deduct 0.5 points. - If the student's answer does not match any string in L_3’, award at least 0.5 points. It is possible that his answer misses some subset in L_3. Depending on the nature of these subsets, this 0.5 can become a 1.5 (see, for example, the last point). Grade at your discretion. - Award 0 points, if the student’s answer matches any infinite subset of L_3’.
(d) Anything equivalent to (0*100*10)*0*100* is worth the full 2 points. Instructions similar to (d) also apply here. Grade at your discretion. Grade at your own discretion. Adding new start and accepting states (1 point) Eliminate q_1 (3 points)