Proof that $\textit{INFINITE}_{\text{DFA}}$ is decidable.(Sipser Q.4.10)

Question

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?

Answer 1

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$.

Answer 2

The intuition is to test if $A$ accepts any word of length greater than the number of its states.

Answer 3

$D$ accepts any string with at least $k$ symbols. So $M$ recognises those strings from $A$ which have more than $k$ symbols. It's obvious that $D$ can be constructed, and there is a simple way ti construct a DFA which recognizes the intersection of the languages of two DFAs: intuitively, run both DFAs simultaneously and accept if both end the scan in an accepting state.

So we know that $M$ can be constructed. And we have an algorithm which can determine whether it is empty. If it is not empty, it contains at least one string with more than $k$ symbols, which must also be a member of $L(A)$, because all its strings have more than $k$ symbols and all its strings are in $L(A)$.

Finally, a DFA with $k$ states which recognises a string with more than $k$ symbols must recognise an infinite number of strings.