Consider the following sets representing computational problems 

   

(a) For the DFA M ₁  with the given state diagram, list all and only P _i  such that (M ₁ ) ∈ P _i  (where 1 ≤ i ≤ 6) 

   

(b) For the DFA M ₂ with the given state diagram, list all and only P _i such that (M ₂ ) ∈ P _i (where 1 ≤ i ≤ 6)

(c) For the DFA M ₃ with the given state diagram, list all and only P _i such that (M ₃ ) ∈ P _i (where 1 ≤ i ≤ 6)

(d) Which one of the following statements is true?

i. P ₅ ⊆ P ₆

ii. P ₆ ⊆ P ₅

iii. EQ _DFA ⊆ P ₆

iv. P ₆ ⊆ EQ _DFA

Transcribed Image Text:

P = {(M) | M is a DFA over (a, b} and L(M) # 0} P = {(M)| M is a DFA over {a, b} and |L(M)| = 1} P= {(M) | M is a DFA over {a, b} and L(M) is finite} P = {(M) | M is a DFA over (a, b} and ab e L(M)} P, = {(M, M") | M and M' are both DFA over {a, b} and L(M) # L(M")} P = {(M, M") | M and M' are both DFA over {a, b} and L(M)C L(M')} P = {(M) | M is a DFA over (a, b} and L(M) # 0} P = {(M)| M is a DFA over {a, b} and |L(M)| = 1} P= {(M) | M is a DFA over {a, b} and L(M) is finite} P = {(M) | M is a DFA over (a, b} and ab e L(M)} P, = {(M, M") | M and M' are both DFA over {a, b} and L(M) # L(M")} P = {(M, M") | M and M' are both DFA over {a, b} and L(M)C L(M')}

Answer rating: 100% (QA)

a M 1 has only one state q 2 Only four strings result in this final state so LM 1 aa ab ba bb So LM ... View the full answer