Four Show a DFA over the alphabet {a, b} for the following language via the construction in the proof of Theorem 1.25 (that Finite State Languages are closed under union) & the footnote 3 on p. 46 (that Finite State Languages are closed under intersection): {w belongs to Sigma^* | w contains an odd number of symbol a's and ends with the symbol b} The class of regular languages is closed under the union operation. In other words, if A_1 and A_2 are regular languages, so is A_1 U A_2. We have regular languages A_1 and A_2 and want to show that A_1 U A_2 also is regular. Because A_1 and A_2 are regular, we know that some finite automation M_1 recognizes A_1 and some finite automaton M_2 recognizes A_2. To prove that A-1 U A_2 is regular, we demonstrate a finite automaton, call it M, that recognizes A_1 U A_2. This is a proof by construction. We construct M from M_1 and M_2. Machine M must accept its input exactly when cither M_1 or M_2 would accept it in order to recognize the union language. It works by simulating both M_1 and M_2 and accepting if either of the simulations accept. How can we make machine M simulate M_1 and M_2? Perhaps it first simulates M_1 on the input and then simulates M_2 on the input. But we must be careful here! Once the symbols of the input have been read and used to simulate M_1, we can't "rewind the input tape" to try the simulation on M_2. We need another approach. Pretend that you are M. As the input symbols arrive one by one, you simulate both M_1 and M_2 simultaneously. That way, only one pass through the input is necessary. But can you keep track of both simulations with finite memory? All you need to remember is the state that each machine would be in if it had read up to this point in the input. Therefore, you need to remember a pair of states. How many possible pairs are there? If M_1 has k_1 states and M_2 has k_2 states, the number of pairs of states, one from M_1 and the other from M_2, is the product k_1 times k_2. This product will be the number of states in M, one for each pair. The transitions of M go from pair to pair, updating the current state for both M_1 and M_2. The accept states of M are those pairs wherein either M_1 or M_2 is in an accept state