## 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.