[ Prepared by Mustafa
Kirac ]
General Announcement
Please give your homework solutions in their given order.
You may lose points because I think some of your solutions are missing.
Please read the postmortem and solutions carefully if you
did not like your score before wanting me to regrade your solutions. Sometimes
I miss or tolerate some of your errors. When I regrade your questions you may
get a lower score as I am going to grade the whole paper again.
If you decided to disapprove your grading, please attach
your graded homework sheet to your next homework with an extra explanation note
on it. I am going to regrade them according to my policy above.
Problem 1.0 [10 points]
- (a)
Many didn’t write any solution (-1)
- (b)
Many created a wrong FSM that does not accept “3343”
- (c) Some
people were tricked by the high precedence of the
% operator in perl. Where in math
you write "q + i mod 2", in perl you write (q + i) % 2. (-1)
Problem 1.1 [10 points]
- Some people forgot to fully
define DFA's. This includes indicating the start state and an arrow for
every possible input from every state.
Problem 1.2 [30 points]
- (c)
Many solution did not accept “0100101”.
- (l)
Zero number of 0s are also even number of 0s.
- (m) Empty
set is {}.A machine accepting e is not empty.
Problem 1.3 [10 points]
- Many
FSM were not correct (-5)
Problem 1.4 [10 points]
- Many
cannot use induction technique or cannot prove anything at all.
Problem 1.5 [10 points]
- Most
of the people forgot to define the machine in detail. You must either show
the FSM in 5 tuple notation or in state diagram.
Problem 1.6 [10 points]
Problem 1.7 [5 points]
- Most
people proves their assumption (for n) instead of accepting it as true and
proving it for n+1.
Problem 1.8 [15 points]
- Many
FSM were not correct (-1/-2 each)
Problem 1.9 [10 points]
- Some
people have wrong data in their table.