Show a Turing Machine accepts all DFAs

Question

You have a Turing Machine $T = \{ \{ A \} \mid A$ is a DFA and $L(A) = \Sigma^* \}$ i.e. the DFA that accepts all languages. Show it's decidable. Can you use the complement of this, the DFA that accepts the empty language which I believe is decidable by Rice's Theorem to show this is decidable? And if so why does that work? Is it because decidable languages are closed under complementation?

Answer 1

T = "On input {A} where A is a DFA

$\quad \quad$1. Mark the Start State of A

$\quad \quad$2. Repeat until no new state get marked

$\quad \quad \quad \quad$2(1). Mark any state that has a transition coming into it from any state already marked

$\quad \quad$3. If all the marked state(s) are accepting state, then $Accept$; otherwise $Reject$"

Suppose B = $\bar{A}$ i.e. L(B)= $\phi$

There are two cases

$Case-1:$

N = "On input {B} where B is a DFA

$\quad \quad$1. Run TM T on {B}

$\quad \quad$2. If T Accepts, $Reject$; and if Rejects, $Accept$"

$\implies$ N is not working correctly

$Case-2:$

M = "On input {B} where B is a DFA

$\quad \quad$1. Mark the Start State of B

$\quad \quad$2. Repeat until no new state get marked

$\quad \quad \quad \quad$2(1). Mark any state that has a transition coming into it from any already marked state

$\quad \quad$3. If no accepting state is marked, then $Accept$; otherwise $Reject$"