3.2 Chapter 1, Sections 1.1-1.2

Complete the following problems:

1. (0.25) For the DFA where Q = {q1, q2, q3}, Σ = {a,b}, δ = {(q1, a, q1), (q1, b, q2), (q2, a, q3), (q2, b, q3), (q3, a, q3), (q3, b, q3)}, q0 = q1, F = {q2}, do the following:

   1. Draw a diagram of the DFA.

   2. Give a formal definition of the language that it recognizes.

   3. For each of following strings, indicate whether it is in the language or not:

      1. ϵ

      2. b

      3. a

      4. aa

      5. ba

      6. bb

      7. baa

      8. aab

      9. babb

      10. baaab

      11. aaaab

      12. aabaa

2. (0.15) Do exercise 1.4(e) in the book. Just give the state diagrams. This is the one that starts with an a and has at most one b.

3. (0.15) Do exercise 1.6(e) in the book. This is the one that starts 0 and has odd length or starts with 1 and has even length.

4. (0.10) Do exercise 1.7(g) in the book. This is the one about the empty language.

5. (0.15) Design a 4-state NFA over the binary alphabet for the language L = {w ∈ {0,1}* | w = 0^m 1^n, m ≥ 1, n ≥ 1} ∪ {ϵ, 0}. Just give the state diagram.

6. (0.20) Start from the NFA from exercise 1.16(b) in the book (the three state machine drawn in a triangle), add a self-loop labeled a to state 2, show the 5-tuple, then convert it to an equivalent DFA. Show the DFA’s state diagram. Remove any unreachable DFA states to simplify and show the result (as a diagram.)