Michael Sipser Edition 3 Exercise 1 Question 4 (Page No. 83)

Question

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

1. $\text{\{w| w has at least three a’s and at least two b’s\}}$
2. $\text{\{w| w has exactly two a’s and at least two b’s\}}$
3. $\text{\{w| w has an even number of a’s and one or two b’s\}}$
4. $\text{\{w| w has an even number of a’s and each a is followed by at least one b\}}$
5. $\text{\{w| w starts with an a and has at most one b\}}$
6. $\text{\{w| w has an odd number of a’s and ends with a b\}}$
7. $\text{\{w| w has even length and an odd number of a’s\}}$