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

Name: ____________________________

• you are allowed up to 5 pages of handwritten notes;
• if you need extra pages, place your name on each extra page;
• the main goal of most questions is to show that you know the corresponding algorithms; so, if you are running of time, just follow the few first steps of the corresponding algorithm;
• each question will be graded on its own merit; so, for example, if when answering to the first part of the question, you got a wrong automaton, but on the second part, you correctly traced the new automaton, you will get full credit for the second part.
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:

• from the state s, symbol # leads to c, symbols m and n lead to si;
• from c, any symbol leads to c; and
• from si, every symbol leads to si.

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

• the word #mn (which this automaton should accept) and
• the word m# (which this automaton should reject).

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:

• Q is the set of all the states,
• Σ is the alphabet, i.e., the set of all the symbols that this automaton can encounter;
• δ: Q x Σ → Q is the function that describes, for each state q and for each symbol s, the state
δ(q, s) to which the automaton that was originally in the state q moves when it sees the symbol s (you do not need to describe all possible transitions this way, just describe two of them);
• q0 is the staring state, and
• F is the set of all final states.

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.