DFA Closure: 1.4 c and f. Do union and intersection for each (use cross product algorithm) Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs fo Original Papers

DFA Closure: 1.4 c and f. Do union and intersection for each (use cross product algorithm)

Each of the following languages is the intersection of two simpler languages. In each part, construct DFAs for the simpler languages, then combine them using the construction discussed in footnote 3 (page 46) to give the state diagram of a DFA for the language given. In all parts, Σ = {a, b}.

c) {w| w has an even number of a’s and one or two b’s}

f) {w| w has an odd number of a’s and ends with a b}

NFA to DFA Algorithm: 1.16

NFA Closure: 1.8a, 1.9a, 1.10a, 1.10c

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)      a. {w| w begins with a 1 and ends with a 0}

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

1.9 Use the construction in the proof of Theorem 1.47 to give the state diagrams of NFAs recognizing the concatenation of the languages described in

a) g. {w| the length of w is at most 5}

b) i. {w| every odd position of w is a 1}

1.10 Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described in a. Exercise 1.6b.

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

Use the construction in the proof of Theorem 1.49 to give the state diagrams of NFAs recognizing the star of the languages described in

m. The empty set

Regular Expression Practice: 1.18

1.18 Give regular expressions generating the languages of Exercise 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)}

 d. {w| w has length at least 3 and its third symbol is a 0}

e. {w| w starts with 0 and has odd length, or starts with 1 and has even length}

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

 g. {w| the length of w is at most 5}

h. {w| w is any string except 11 and 111}

 i. {w| every odd position of w is a 1}

 j. {w| w contains at least two 0s and at most one 1}

k. {ε, 0}

l. {w| w contains an even number of 0s, or contains exactly two 1s}

m. The empty set

n. All strings except the empty string

RE to NFA Practice: 1.19a, 1.19b

1.19 a) Use the procedure described in Lemma 1.55 to convert the following regular expressions to nondeterministic finite automata.

a. (0 ∪ 1)^ ∗000(0 ∪ 1)^ ∗

b. (((00)^ ∗(11)) ∪ 01)^ ∗