CS 3350 Automata, Computability, and Formal Languages
Spring 2020, Test 1

Name: ____________________________

General comments:

Good luck!

1-3. Let us consider an automaton for recognizing words starting with a pound sign #. For simplicity, let us only consider letters m and n. This automaton has 3 states: start (s), correct (c), and sink (si). Start is the starting state, correct is the only final state. The transitions are as follows:

1. Trace, step-by-step, how this finite automaton will check whether the following two strings start with #:

2. Use the above tracing to find the parts x, y, and z of the word #m#n corresponding to the Pumping Lemma. Check that the "pumped" word xyyz will also be accepted by this automaton.

3. Write down the tuple <Q, Σ, δ, q0, F> corresponding to this automaton:

4-5. Let A be the automaton described in Problem 1-3. Let B be an automaton that accepts all the strings that contain only # and m but not any other symbols. This automaton has two states: the start state which is also a final state, and the sink state. The transitions are as follows:
  • from the start state, # or m leads back to the start state, n leads to the sink;
  • from the sink state, any symbol leads back to the sink.

4. Use the algorithm that we had in class to describe the following two new automata:

  • the automaton that recognizes the union A U B of the two corresponding languages, and
  • the automaton that recognizes the intersection of the languages A and B.

5. Test these two new automata step-by-step on the following words:

  • test the union automaton on the example of the word m# (that it should accept);
  • test the intersection automaton on the example of the words #mn (that it should reject).

6-7.

6. Use the general algorithm that we learned in class to design a non-deterministic finite automaton that recognizes the language #(m U n U #)*:

  • first, describe the automata for recognizing #, m, and n;
  • then, combine them into the automata for recognizing the union m U n, (m U n) U #, and the Kleene star (m U n U #)*;
  • finally, combine the automaton for # with an automaton for the Kleene star into an automaton for recognizing the desired composition of the two languages.

7. Use the general algorithm to transform the resulting non-deterministic finite automaton into a deterministic one.

8-9. Use a general algorithm to transform the finite automaton B from Problem 4-5 into the corresponding regular expression.

10. Prove that the language L of all the words that have equal number of m's and n's is not regular.