CSC 8510 Theory of Computing
Solutions to selected exercises on pages 83-88

Here are solutions to some of the exercises that I suggested; I've made some fairly obvious substitutions for the (unavailable) Greek letters: S = capital sigma, d = delta, e = empty string.

1.1
    a  The start state of M₁ is q₁.
    b  The set of accept states of M₁ is {q₂}.
    c  The start state of M₂ is q₁.
    d  The set of accept states of M₂ is {q₁, q₄}.
    e  M₁, given aabb, goes through q₁ (start), q₂, q₃, q₁, q₁.
    f  M₁ does not accept the string aabb.
    g  M₂ does accept the empty string.

1.2 Formal descriptions of M₁ and M₂ are:
        M₁ = ({q₁, q₂, q₃}, {a,b}, D1, q₁, {q₂}), where
        D1 = {d(q₁,a)=q₂, d(q₁,b)=q₁, d(q₂,a)=q₃, d(q₂,b)=q₃, d(q₃,a)=q₂, d(q₃,b)=q₁}

        M₂ = ({q₁, q₂, q₃, q₄}, {a, b}, D2, q₁, {q₁, q₄}), where
        D2 = {d(q₁,a)=q₁, d(q₁,b)=q₂, d(q₂,a)=q₃, d(q₂,b)=q₄, d(q₃,a)=q₂, d(q₃,b)=q₁, d(q₃,a)=q₃, d(q₃,b)=q₄}

1.3, 1.4, 1.5 -- I don't have good tools to draw pictures on this PC. Ask me in class and I'll do some.

1.10
a   Actually, there's practically nothing to do here. A DFA has a transition from every state for every possible input symbol (by definition), so any string over those symbols that you give to a DFA will end up in some state. The strings that end in a final state will be accepted, so in the complement of the language they should be rejected; the strings that end up in a nonfinal state will be rejected, so in the complement they should be accepted. Just reversing the final and nonfinal states does this.
b   The NFA shown in (a) of exercise 1.12 accepts the string "a"; if the final and nonfinal states were reversed, it would still accept "a". However, the class of languages recognized by NFAs (which is the same as the class of languages recognized by DFAs) is closed under complement--it just takes a little more work to get the right machine. First, convert the NFA to a DFA, then reverse the final and nonfinal states in that DFA.

1.15  Note: "S" is capital sigma, "e" is the empty string.