Fall 2017, Test 1

General comments:

- 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.

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 q
_{1}which is a start state and a final state, and another state a state q_{2}. - In the state q
_{1}, 0 leads to q_{2}, and 1 leads to q_{1}. - In the state q
_{2}, 0 leads to q_{2}, and 1 leads to q_{1}.

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 q
_{1}which is also final, a state q_{2}, and a final state q_{3}. - When you see 0,
from q
_{1}you move to q_{3}, from q_{2}you move to q_{1}, and from q_{3}you move to q_{2}. - When you see 1, from q
_{1}you move to q_{2}, from q_{2}you move to q_{3}, and from q_{3}you move to q_{1}.

6. Prove that the language {a^{n}b^{n+1}} = {Λ,
abb, aabbb, aaabbbb, ...} is not regular.