CS 3350 Automata, Computability, and Formal Languages
Fall 2018, Test 1

Last 4 digits of your UTEP ID number: ____________________________

General comments:

Good luck!

1-4. In class, we studied an automaton for recognizing valid Java identifiers. This automaton has 3 states: start (s), identifier (i), and error (e). Start is the starting state, identifier is the only final state. The transitions are as follows:

1. Is any of the three states a sink state? Explain your answer.

2-3. Trace, step-by-step, how this finite automaton will check whether the following two words (sequences of symbols) represent a valid Java identifier:

4. Write down the tuple <Q, Σ, δ, q0, F> corresponding to this automaton:

5. Draw an automaton for recognizing all possible binary signed integers. Trace this automaton on the example of numbers +10 (that it should accept), −10 (also accepted), and 10 (should be rejected).

6-8. Let A be an automaton described in Problem 1. Let B be the following automaton that accepts all the strings that contain only letters but not any other symbols. This automaton has two states: the start state which is also a final state, and the sink state. The transitions are as follows:
  • from the start state, any letter leads back to the start state, every other symbol leads to sink;
  • from the sink state, any symbol leads back to sink.

6. Use the algorithm that we had in class to describe the following two new automata:

  • the automaton that recognizes the union A U B of the two corresponding languages, and
  • the automaton that recognizes the intersection of the languages A and B.

7-8. Test these two new automata step-by-step on the following words:

  • test the union automaton on the example of the words Var (that it should accept) and 2words (that it should reject);
  • test the intersection automaton on the example of the words Var (that it should accept) and Var2 (that it should reject).

9-10. Use the general algorithm that we learned in class to design a non-deterministic finite automaton that recognizes the language (0 U 1)(1 U 2):
  • first, describe the automata for recognizing 0, 1, and 2;
  • then, combine them into the automata for recognizing the unions 0 U 1 and 1 U 2;
  • finally, combine the two union automata into an automaton for recognizing the composition
    (0 U 1)(1 U 2) of the two union languages.