CS 3350 Automata, Computability, and Formal Languages
Fall 2015, Quiz Based on Test 1, 3-4:20 pm version

Name: __________________________________________________________

3. Let us start with the following non-deterministic finite automaton. It has 4 states q1, ..., q4. The state q1 is a start state, the states q1 and q3 are final (accept) states.

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 = {words that have exactly the same number of a's, b's, and c's}.
This language includes words Λ, abc, cba, abcabc, aabbcc, etc.