Spring 2016, Test 1

1-2. 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
same language.

3. 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 both a start state and a final state, and
a 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.

4. On the example of the automaton from Problem 3, explain, in detail,
how the sequence 010100 will be presented as xyz according to the
pumping lemma. For this sequence, check -- by tracing
step-by-step -- that
the sequence xy^{i}z for i = 2 is indeed accepted by the
automaton.

5. Use the Pumping Lemma to prove that the language L consisting of
all the words of the type *waw* is not regular, where *a* is a letter and
*w* can be any word.
Here:

- if
*w*is an empty string, we get the word*a*, - if
*w*is*ab*, we get*abaab*,

6. Use the general algorithm that we had in class to design a
context-free grammar which generates exactly the words accepted by
the automaton from Problem 3. Show how the word 010100 will be
generated by this grammar.

7. (For extra credit) Use the general algorithm to transform the
grammar from Problem 6 into a pushdown automaton.