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.