Spring 2020, Test 1

General comments:

- 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.

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, Σ, δ, q_{0},
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); - q
_{0}is the staring state, and - F is the set of all final states.

- 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.