Define a decision procedure for each of the following questions.Argue that each of your decision procedures gives the correctanswer 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 β dothere exist any even length strings that are in L(α) but not L (β)?
  5. Let Σ = {a, b} and let α be a regularexpression. Does the language generated by a contain all the evenlength strings in Σ*
  6. Given an FSM M and a regular expression α, isit true that both L(M) and L(α) are finite andM accepts exactly two more strings than αgenerates?
  7. Let Σ = {a, b} and let α and β be regularexpressions. Is the following sentence true: (L(β)=a*)V(ω(ω∈ {a,b}*|ω| even) -> ωL(α)).
  8. Given a regular grammar G, is L(G)regular?
  9. Given a regular grammar G, does G generateany odd length strings?