Marking Scheme and Common Errors, Q1 & Q3 Test1
Liuxing Kan

Q1:

a. If you draw a state diagram which can accept at least one string in
L, you will get 4 points.  

b. If your state diagram is DFA, you will get 1 points

c. If your DFA can recognizes all strings in L, you will get 5 points.

Q3:

a. If you have a idea that every regular language can be recognized by
an all-path-NFA, you will get 5 points.

b. If you have a idea that every all-path-NFA can be converted to an
equivalent DFA, you will get 5 points.

c. If your proof is not right, but you draw a conclusion that
all-paths-NFAs recognize the class of regular language, you will get 1
points.

Common Errors(for your reference, and for Tim's office hour)

Q1: A lot of students get full points or nearly full points. Some
students give a NFA state diagram or try to draw an infinite automata.

Q3: Only a few students get full points. Some have a proof idea, but
don't express it clearly. And some students attempt to use induction
or transition function to prove.