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 q1, ..., q4. The state q1 is a start state, the states q2 and q4 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 = {anbncn: n = 0, 1, 2, ... } = {Λ, abc, aabbcc, aaabbbccc, ...}.