CS 3350, Spring 2017, Test 1: typical mistakes

Problem 1-2:

* Next time, as I suggested during a preview, please construct a
non-deterministic automaton step by step, and show all the steps,
as we do in class. If all I see is a wrong non-deterministic
automaton, then all I know is that something is wrong. If I see it
step by step, it may be that you do not know the algorithm, but
made a minor mistake in one of the steps -- so you will get a lot
of partial credit.

* In a deterministic automaton, for each state and for each
symbol, there should be an arrow indicating what to do if in this
particular state, we see this particular symbol.

* Concatenation AB of two strings or of two languages is NOT
commutative: as I mentioned during the preview, if A is "John" and
B is "Smith", then AB is "JohnSmith" but BA is "mithJohn", these
are two different strings.

* Mistakes in the algorithm: mistakes in union, concatenation, and
Kleene star

Problem 3-4: do not confuse empty string /\ and empty set, they
are different.

Problem 5: for each state of the new automaton and for every
symbol, there should be an arrow indicating what to do if in this
particular state, we see this particular symbol.

General comments:

* If you cross our zero so that it looks like an empty set use {}
notation for the empty set, to avoid confusion. Some students got
confused themselves.

* For this test, I am grading liberally, giving a lot of extra
credit, since this is a new and difficult topic; however, if you
repeat the same mistakes on the corresponding part of the final
exam, the grade will be much lower.