Question

Question:Let${\mathbf{\text{INFINITE}}}_{\mathbf{DFA}}\mathbf{=}\left\{\left(A\right)|\mathrm{AisaDFAandL}\left(A\right)\mathrm{isaninfinitelanguage}\right\}\mathbf{.}$Show that$\mathit{I}\mathit{N}\mathit{F}\mathit{I}\mathit{N}\mathit{I}\mathit{T}{\mathit{E}}_{\mathbf{D}\mathbf{F}\mathbf{A}}$ is decidable.

Short answer

Answer

${\text{INFINITE}}_{DFA}=\left\{\left(A\right)|AisaDFAandL\left(A\right)isaninfinitelanguage\right\}.$is $INFINIT{E}_{DFA}$is decidable is proved.

Step-by-step solution

Step 1: Decidable property.

Decidable property of any language is defined as whose solution is present. And in other words the problem is solvable is called decidable property.

Step 2:

The${\text{INFINITE}}_{DFA}=\left\{\left(A\right)|AisaDFAandL\left(A\right)isaninfinitelanguage\right\}.$And this is $INFINIT{E}_{DFA}$is decidable is shown as,

Turing machine INFINITE $<PDA>:$

On input $<M>,$

1. Convert given $<M>,$to context free language using algorithm for converting Pushdown deterministic automaton to context free language.

2. Run INFINITE context free language, If, it accepts then accept, else if it rejects reject.

The following Turing machine decides INFINITE deterministic finite automata.

1. Let k be the number of states of

2. Construct deterministic finite automaton that accepts all strings of length or more.

3. Construct a DFA such that,

$L\left(M\right)=L\left(A\right)\cap L\left(D\right).$

4. Test, $L\left(M\right)=\varnothing$using the EDFA decider machine.

5. If T accepts, reject; if T rejects, accept.”

This algorithm works because a deterministic finite automaton that accepts infinitely many strings must accept arbitrarily long strings. Therefore, this algorithm accepts such Deterministic finite automatons. Conversely, if the algorithm accepts a Deterministic finite automaton Deterministic finite automaton, the Deterministic finite automaton accepts some string of length k or more, where k is the number of states of the Deterministic finite automaton. This string may be pumped in the manner of the pumping lemma for regular languages to obtain infinitely many accepted strings.

Hence, the problem is solvable and decidable.