#### 3.2` `Chapter 1, Sections 1.1-1.2

Complete the following problems:

(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:

Draw a diagram of the DFA.

Give a formal definition of the language that it recognizes.

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

ϵ

b

a

aa

ba

bb

baa

aab

babb

baaab

aaaab

aabaa

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

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

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

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

(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.)