Consider the following sets representing computational problems Prove that each of these four problems is decidable P

Consider the following sets representing computational problems

Prove that each of these four problems is decidable

Transcribed Image Text:

P₂ = {(M) | M is a DFA over {a,b} and |L(M)| = 1} P₁ = {(M) | M is a DFA over {a,b} and ab € L(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')} P₂ = {(M) | M is a DFA over {a,b} and |L(M)| = 1} P₁ = {(M) | M is a DFA over {a,b} and ab € L(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')}

Answer rating: 100% (QA)

To prove that each of the four problems P2 P4 P5 and P6 is decidable we need to show that there exists a Turing machine that can decide whether an input belongs to each problem In other words we need ... View the full answer