CS 3350, Quiz 1, September 1, 2016

Name: ____________________________________________________________________

No notes allowed

1. Design an automaton that accepts binary sequences which only have 0s and not 1s. Trace your automaton on two examples: a sequence 000 (which should be accepted) and a sequence 001 (which should be rejected).

2-3. Use a similar construction to design an automaton that accepts only binary sequences that consists of 1s (no 0s allowed). Use a general algorithm that we had in class to design a new automaton that recognizes the union of these two languages, i.e., which accepts either sequences consisting of all 0s or sequences consisting of all 1s. Trace you new automaton on the example of sequence 111.

4. (For extra credit) Use a general algorithm to transform the following non-deterministic automaton into a deterministic one: this automaton has three states, starting state q0 and two states q1 and q2. The state q2 is the only final state. In the state q0, when we see 0, we can go to q1 or to q2. From q1, we can jump to q0.