Use the construction in the proof of Theorem 1.45 to give the state diagrams of NFAs recognizing the union of the languages described in

a. Exercises 1.6a and 1.6b.

b. Exercises 1.6c and 1.6f.

Exercises 1.6

a. {w| w begins with a 1 and ends with a 0}

b. {w| w contains at least three 1s}

c. {w| w contains the substring 0101 (i.e., w = x0101y for some x and y)}

f. {w| w doesn’t contain the substring 110}

Theorem 1.45

Transcribed Image Text:

N N1 N2