1. (12 points) Consider the following sets representing computational problems (numbering is from the warmup assignment)

   P2 ={M|M isaDFAover{a,b}and|L(M)|=1} P4 ={M|M isaDFAover{a,b}andabL(M)} P5 = {M,M | M and M are both DFA over {a,b} and L(M) = L(M)} P6 = {M,M | M and M are both DFA over {a,b} and L(M) L(M)}

   Prove that each of these four problems is decidable.

   

1. (12 points) Consider the following sets representing computational problems (numbering is from the warmup assignment) P 1(M) | M is a DFA over {a, b} and L(M)-1} P M)M is a DFA over (a, b) and ab e L(M)) P's (M. !'> 1 M and M, are both DFA over {a, b} and L(M) Po-{(N1, ,> | M and M, are both DFA over {a,b) and L(M) L(M')} L(M')} Prove that each of these four problems is decidable. 1. (12 points) Consider the following sets representing computational problems (numbering is from the warmup assignment) P 1(M) | M is a DFA over {a, b} and L(M)-1} P M)M is a DFA over (a, b) and ab e L(M)) P's (M. !'> 1 M and M, are both DFA over {a, b} and L(M) Po-{(N1, ,> | M and M, are both DFA over {a,b) and L(M) L(M')} L(M')} Prove that each of these four problems is decidable