Question

Show that ${\mathbf{ALL}}_{\mathbf{DFA}}\mathbf{is}\mathbf{in}\mathbf{P}.$

Short answer

The $AL{L}_{DFA}$isin showed.

Step-by-step solution

Step 1:To Randomized the Class - P

On such a randomized single-tap Turing machine, $P$ is indeed a class of languages that can be answered in polynomial time.

$AL{L}_{DFA}=\{<A>AisaDFAthatrecognies\backslash \mathrm{mathop}{\sum }^{*}\}$

$E_{DFA}=\{<A>AisaDFAandL\left(A\right)=\varnothing \}$

is determined by a Turing – machine $\left(TM\right)$

Let $E$ be the Turing machine that determines$E_{DFA}$

Let $R$ be the Turing machine that determines $AL{L}_{DFA}$

The R – Algorithm Steps

The algorithm of $R$ is as follows:

:$R=\text{'}\text{'}Oninput<A>,whereAisaDFA$

1. Construct a $DFA B$that recognizes$L\left(\overline{A}\right)$, by swapping accept and non – accepting states

2. Run the $TME$on input$<B>$, where E determines$E_{DFA}$.

3. If $E$ accepts, then accept

4. If $E$ rejects, then reject.”

Clearly the$TMR$ determines$AL{L}_{DFA}$ in polynomial time.Therefore, $AL{L}_{DFA}$is in $P$.