id: 88796294

General comment: Unless explicitly specified, each homework should be turned in on a sheet of paper: draw an automaton like we did in class and like the book does, do whatever else needed, add the last 4 digits of your ID number on top and turn it in by the beginning of the class on the day when the homework is due.

1. In class, we studied an automaton for recognizing signed or unsigned binary integers. This automaton has 4 states: start (st), sign (si), integer (i), and error (e). Start is the starting state, integer is the only final state. The transitions are as follows: from st, 0 or 1 lead to i; + or lead to si, every other symbol leads to e; from si, 0 or 1 lead to i, every other symbol leads to e; from i, 0 or 1 lead to i, every other symbol leads to e; from e, every symbol leads to e. Trace, step-by-step, how this finite automaton will check whether the following two words (sequences of symbols) represent syntactically correct binary integers: the word 0 (which this automaton should accept) and the word 00 (which this automaton should reject).

2. In class, we had yet another finite automaton for recognizing signed or unsigned binary integers. This new automaton has 5 states: the starting state start (st), the state sign_read (sr), the state signed_integer (si), the state unsigned_integer (u), and the sink (error) state e. This automaton has two final states: si and u. The transitions are as follows: from st, + or lead to sr, 0 or 1 lead to u, every other symbol leads to e; from sr, 0 or 1 lead to si, any other symbol leads to e; from si, 0 or 1 lead to si, any other symbol leads to e; from u, 0 or 1 lead to u, any other symbol leads to e; from e, any symbol leads to e. Write down the tuple corresponding to this automaton: Q is the set of all the states, is the alphabet, i.e., the set of all the symbols that this automaton can encounter; : Q x Q is the function that describes, for each state q and for each symbol s, the state (q, s) to which the automaton that was originally in the state q moves when it sees the symbol s (you do not need to describe all possible transitions this way, just describe two of them); q0 is the staring state, and F is the set of all final states.

3. Similarly to the automaton from Problem 1 (that we analyzed in class), draw an automaton for recognizing all possible signed and unsigned integers (not necessary binary), so that this automaton will also recognize numbers like 32, +32, and 32.