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

Name: __________________________________________________________

• you are allowed up to 5 pages of handwritten notes;
• if you need extra pages, place your name on each extra page;
• the main goal of most questions is to show that you know the corresponding algorithms; so, if you are running of time, just follow the few first steps of the corresponding algorithm;
• each question will be graded on its own merit; so, for example, if on one stage, you got a wrong non-deterministic automaton, but on the second stage, you correctly transform it into a deterministic one, you will get full credit for the second stage.
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.
• This automaton has two states: a state q1 which is a start state and a final state, and another state a state q2.
• In the state q1, 0 leads to q2, and 1 leads to q1.
• In the state q2, 0 leads to q2, and 1 leads to q1.

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.