Spring 2017, Test 1

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.

- This automaton
has two states: a state q
_{1}which is a start state, and a state q_{2}which is a final state. - In the state q
_{1}, 1 leads to q_{2}, and 0 leads to q_{1}. - In the state q
_{2}, 1 leads to q_{2}, and 0 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}, and the two final states q_{2}and q_{3}. - When you see 0,
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}. - When you see 1, 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}.