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

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_{1} and
q_{3} are final (accept) states.

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

6. Use the Pumping Lemma to prove that the following language is
not regular: L = {words that have exactly the same number
of a's, b's, and c's}. This language includes words
Λ, abc, cba, abcabc, aabbcc, etc.