CS 3350 Automata, Computability, and Formal Languages
Fall 2016, Test 1

Name: __________________________________________________________

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 a start state, and a state q2 which is a final state. 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.

4. On the example of the automaton from Problem 3, explain, in detail, how the sequence 001100 will be presented as xyz according to the pumping lemma. For this sequence, check -- by tracing step-by-step -- that the sequence xyiz 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 www is not regular, where w can be any word. Here:
  • if w is an empty string, we get the word Λ,
  • if w is ab, we get ababab,
etc.

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 001100 will be generated by this grammar.