The answer of the question is given below:
But I could not understand the intuition behind 2 and 3 in the description of the machine below, could anyone explain this for me please?
[Math] Proof that $\textit{INFINITE}_{\text{DFA}}$ is decidable.(Sipser Q.4.10)
computabilitycomputational complexityformal-languagesturing-machines
Related Question
- [Math] Show that of Turing decidable languages is closed under concatenation.
- [Math] Show that single-tape TMs that cannot write on the portion of the tape containing the input string recognizes only regular languages.
- [Math] Prove that the following language is decidable / undecidable
- Prove that if L is decidable then half(L) is decidable too
Best Answer
For a DFA $D$ with $k$ states, we have that $L(D)$ is infinite if and only if $D$ accepts some string $\omega$ of length $k \leq |\omega| \leq 2k-1$. So to test if $L(D)$ is infinite, we enumerate all strings with length between $k$ and $2k-1$. If $D$ accepts one of these strings, $L(D)$ is infinite. Otherwise, $L(D)$ is finite. The idea, as described in the answer you provided, is that a string with length between $k$ and $2k-1$ can be pumped up repeatedly, to generate infinitely many strings. So we can equivocally test if the DFA $D$ accepts any string of length at least $k$. This is what the answer is doing.
In particular, steps (2) and (3) are used to test if the DFA $A$ accepts any string of length at least $k$.