1) Define a decision procedure for each of the following questions. Argue that each of your decision procedures gives the correct answer and terminates.
a) Given two DFSMs M1 and M2, is L(M1) = L(M2)^R?
b) Given an FSM M and a regular expression α, is it true that L(M) and L(α) are both finite and M accepts exactly two more strings than α generates?