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

Name: __________________________________________________________

General comments:

Good luck!

1-2. Use a general algorithm to design a non-deterministic finite automaton recognizing the language 0(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 which is also final, a state q2, and a final state q3.
  • When you see 0, from q1 you move to q3, from q2 you move to q1, and from q3 you move to q2.
  • When you see 1, from q1 you move to q2, from q2 you move to q3, and from q3 you move to q1.
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.

6. Prove that the language {anbn+1} = {Λ, abb, aabbb, aaabbbb, ...} is not regular.