Let M1=(K1, ?, ?1, s1, A1) and M2=(K2, ?, ?2, s2, A2) be DFSMs that accept the regular languages L1 = L(M1) and L2= L(M2).

a. Show that L = L1 ? L2 is regular by carefully constructing a DFSM M=(K, ?, ?, s, A) such that L=L(M). The idea is that each state of M is an ordered pair of states from the other machines. Give the details of the construction (i.e. define each of the five parts of M) using precise mathematical notation.

HINTS:

i.The construction from Sessions 7-8 of the minimal DFSM based on the equivalence classes of a regular language can give you a model for how to express this. But there is probably no place for MyhillNerode style equivalence classes in this particular problem or its solution. Your construction of the 5 parts of M should be based on the 5 parts of M1 and M2.

ii. The key to the construction is figuring out what the transition function ? for the intersection machine should be, based on ?1 and ?2 from the original machines. iii.Cartesian product of states.

b. Let M1 be the 3-state DFSM that accepts { w?{a,b}* : length of w is a multiple of 3}, and let M2 be the 3- state DFSM whose diagram is shown on page 58 of the textbook. M2 accepts { w?{a,b}* : every a in w is followed by a b}. Using your construction in part a, show a transition table or transition diagram for the machine (based on your construction in part a) that accepts the intersection of the languages accepted by M1 and M2.

c. Carefully prove that L=L(M). You will need to use mathematical induction (induction on the length of a string) somewhere in your proof. There will be some similarities between the general approach of this proof and the L=L(M) proof for the minimal DFSM construction, but not many similarities in the details. The similarity is that you will need to prove a lemma by induction that is more general than what is needed to solve this problem, then use a special case of that lemma to get the desired result.

What you need to show: Computations in your new DFSM simultaneously mirror computations in the two original DFSMs, and accept iff both computations from the original machine would accept.

Hint for the lemma: Ultimately we only care about computations that begin at the start state. But it is difficult to show what we need by induction if we only consider those. SO you need to make and prove a statement about the relationship between paths through the new DFSM (starting at any state) and paths in the original DFSMs.

Writing this proof: Probably by the time you get to this point, how the new DFSM works will be obvious. Then you have this problem about half done. The issue now is how to carefully write it up, using one of the notations for a computation (the textbook's ? notation or the ? notation described below) and the notation of your constructions from part a,