Define a decision procedure for each of the following questions. Argue that each of your decision procedures gives the correct answer and terminates.

1. Given two DFSMs M1 and M2, is L (M1) = L (M1)^R
2. Given two DFSMs M1 and M2 is |L (M1)l < | L (M2)|?
3. Given a regular grammar G and a regular expression is L (G) = L ()?
4. Given two regular expressions and do there exist any even length strings that are in L () but not L ()?
5. Let = {a, b} and let be a regular expression. Does the language generated by a contain all the even length strings in *
6. Given an FSM M and a regular expression , is it true that both L(M) and L() are finite and M accepts exactly two more strings than generates?
7. Let = {a, b} and let and be regular expressions. Is the following sentence true: (L()= a*)V(( {a, b}*|| even) -> L()).
1. Given a regular grammar G, is L(G) regular?
10. Given a regular grammar G, does G generate any odd length strings?