CS 3350 Automata, Computability, and Formal Languages
Spring 2017, Test 1

Name: __________________________________________________________

1-2. Use a general algorithm to design a non-deterministic finite automaton recognizing the language 1(1* U 0). After that, use the general algorithm to design a deterministic finite automaton recognizing this same language.

3-4. Use a general algorithm to transform the following finite automaton into the corresponding regular expression.

5. Let A be a language recognized by the automaton from Problem 3, and let B be the language corresponding to the following automaton:
  • This automaton has 3 states, the starting state q1, and the two final states q2 and q3.
  • When you see 0, from q1 you move to q2, from q2 you move to q3, and from q3 you move to q1.
  • When you see 1, from q1 you move to q3, from q2 you move to q1, and from q3 you move to q2.
Use the algorithm that we learned in class, with pairs of states from two automata as states of the new deterministic automaton, to describe the automata recognizing the union and the intersection of these two languages.