[Prepared by Mustafa Kirac]
Scores
|
PS
|
Average
|
Median
|
High
|
|
0
|
106
|
115
|
140
|
|
1
|
107
|
111
|
120
|
|
2
|
98
|
101
|
119
|
Problem 2.0 [20 points]
- a)
- Most people correctly
gave all observed computation paths for the inputs.
- Each missing path cost
(-1) point.
-
- b)
- Some people forgot to
summarize the observed computation paths.
- Each missing path cost
(-1) point.
- Most people forgot to
turn in the path for ε (-1)
- c)
- A few people forgot to
turn in the output for 101, 1101, aaa,
aaaaa, and ε.
- Some people did not
give a printout for the output (-5)
- Each incorrect output
lost (-1)
Problem 2.1 [10 points]
- Some people forgot to
eliminate non-reachable states. (0)
- Some people had incorrect notations.
Problem 2.2 [20 points]
- Some people gave only
drawings and forgot the proof part (-10)
- Some people gave correct
proof but incorrect FSMs. (-2 per FSM)
Problem 2.3 [20 points]
- Some people gave only
drawings and forgot the proof part (-10)
- Some people gave correct
proof but incorrect FSMs. (-2 per FSM)
- A few people created an NFA
accepting strings length more than 3. (-2)
Problem 2.4 [10 points]
- Most people got this one
right.
- DFAs
with small errors lost (-2) per machine.
Problem 2.5 [10 points]
- Almost everyone got the NFA but
some people lost points for not describing the DFA formally (-2)
Problem 2.6 [10 points]
- Most of the class got this
problem wrong so I tolerated small errors.
Problem 2.7 [10 points]
- Most people redefined
acceptance, but did not redefine Δ-hat.
- Whatever the definition one
gives, it must force an ε-closure step
before and after processing each input symbol.
- A quarter of the class gave
something but not a proof (between -5 and -10)
Problem 2.8 [10 points]
- a) Some people didn’t put
itself into the state’s epsilon-closure or the closure was completely
incorrect (-1)
- b) Quarter of the class
thought that the machine accepted all strings of length 3 or less. (-2)
- c) As the set in the part b
is wrong, the DFA became incorrect, too. (-2)