Automata, Computability, and Formal Languages
Test 1, 3-4:20 pm version
1. Prove that the cubic root of 5 is irrational.
2-3. Use a general algorithm to design a non-deterministic finite
automaton recognizing the language
1 U (0*
1). After that, use the general algorithm
to design a deterministic finite automaton recognizing this
4. Use a general algorithm to transform the following finite
automaton into the corresponding regular expression. This automaton
has two states: the starting state q1 and the final state q2. In the state q1, 1 leads to
q2, and 0 leads to q1. In the state q2, 1 leads to q2, and 0 leads to q1.
5. On the example of the automaton from Problem 4, explain, in detail,
how the sequence 10101 will be presented as xyz according to the
pumping lemma. For this sequence, check -- by tracing
step-by-step -- that
the sequence xyi
z for i = 2 is indeed accepted by the
6. Use the Pumping Lemma to prove that the language L consisting of
all three-times repetitions www is not regular.