## CS
3350 Automata, Computability, and Formal Languages

Fall
2015, Quiz Based on Test 1, 12-1:20 pm version

Name: __________________________________________________________
3. Let us start with the following non-deterministic finite
automaton. It has 4 states q_{1}, ..., q_{4}. The
state q_{1} is a start state, the states q_{2} and
q_{4} are final (accept) states.

- We have jumps
from q
_{1} to q_{2} and from q_{3} to
q_{4}. - When we see 0, we can go from q
_{1} to
q_{1} and to q_{3}. - When we see 1, we can go
from q
_{2} to q_{1} or to q_{4}.

Use
the general algorithm to design a deterministic finite automaton
corresponding to this non-deterministic one.

6. Use the Pumping Lemma to prove that the following language is
not regular:

L =
{a^{n}b^{n}c^{n}: n = 0, 1, 2, ... } =
{Λ, abc, aabbcc, aaabbbccc, ...}.