1. Draw the GNFA for the DFA M = {Q, , , q0, F} where

Q = {q0, q1}; = {a, b}; F = {q1}

(q0, a) = q0; (q0, b) = q1; (q1, a) = q1; (q1, b) = q0;

2. Consider the strings over the decimal digits that represent an unsigned base-10 integer

that is processed beginning with the most-significant digit. Draw a DFA that accepts this

string if the integer is evenly divisible by 5.

3. Construct a DFA that recognizes the following language over the alphabet {a,b}.

L = {w | w has an even number of as, each of which is immediately followed by a b}

4. Draw a finite automaton that accepts the language over the alphabet {a,b} in which all

strings have an even length and an odd number of as.

5. Construct a DFA that recognizes the following language over the alphabet {a,b}.

L = {w | w has an even number of as, no two of which are consecutive}