**********************
Midterm Grading Scheme
**********************
*******************
Q1.a: Lin and James
*******************
Overall Feedback: Most students got this very easily. There were a lot of creative solutions here! There were a number of students
who had slightly redundant expressions, an example being (b*(aa)*b*)*, which we did not penalize, though expressions were overly long or
redundant were slightly penalized. There are cases where marks were taken off for multiple reasons.
– 1 For overly redundant expressions
– 2 For very long and convoluted expressions
– 4 Using \cup (Union) instead of +. Unions are not a part of the regular expressions vocabulary.
– 4 One logical mistake, still showing an understanding of the material. (As example missing that the (aa)*b* pattern could repeat)
– 8 Logical mistake, showing some lack of understanding (As example, the regex doesn’t capture very simple cases such as ‘baab’)
************************
Q1.b: Roland and Johanna
************************
Correct 4 state DFA: -5
Missing transition arrows or state labels: – (2 or 3), depending on how many missing
Slightly wrong 3 state DFA (e.g. one wrong transition): -7
Very wrong 3 state DFA (e.g. many wrong transitions): -12
Two state DFA: -15
*********************************************
Q2: Dr. Panangaden, Florestan, Lin, and James
*********************************************
First off: The vast majority of people chose a string with p-2 in it..but what if p=1? We didn’t take points off for that, but the correct version would have been a^p+2b^p and not a^pb^p-2.
If you chose a string that was not in the language to begin with but your reasoning was sound, you should have gotten -20pts.
If you made assumptions on what string the devil chooses (for example assumed y=a^1 instead of a general a^k) you should have lost -15pts.
For minor confusions of mistakes we only took 5points off when the general idea was clearly right.
**
Q3
**
Right or wrong, each out of 4.