# How do I show that this DFA accepts this string?

We are given some DFA $M = (Q, \Sigma, \delta, s, F)$, with $l$ number of states in $Q$, where $M$ accepts a string $w \in \Sigma^*$ such that $|w| \geq l$.

I want to show that if there are infinitely many strings accepted by $M$, then it must also accept some string $w'$ such that $l \leq |w'| < 2l$.

I want to try to use a proof by contradiction, but then it would appear too simple. For example, suppose for contradiction purposes we have infinitely many strings accepted by $M$ but it only accepts some string $w'$ with $|w'| < l$ or $|w'| \geq 2l$.

In the first case, $|w'| < l$ would mean the $w$ is not accepted M already, so this is a contradiction (should I stop here and conclude?).

In the second case, if $|w'| \geq 2l$, then the contradiction is false.

How do I reconcile these differences?

• Hint: Prove something stronger, namely that if $M$ accepts infinitely many strings then for every $k$ it accepts at least one word with $k \le |w| < k+l$. (Consider the shortest strong of length at least $k$ that the automaton accepts). Commented Apr 12, 2018 at 18:10
• As written the question is trivial - take $w'=w$. Do you mean to set $w'\neq w$ as a condition, or $l\lt |w'|$ rather than $\leq$? Commented Apr 12, 2018 at 18:18
• @StevenStadnicki: $w'=w$ is not necessarily a solution, because it is not assumed that $|w|<2l$. Commented Apr 12, 2018 at 18:19
• Ahhh, I missed that. That makes good sense, thank you. Commented Apr 12, 2018 at 18:23
• Thanks everyone. Considering the shortest string of length $k$, I have quite simply the original statement, I think, where $k = 0$, which I know must be true since it's provided, so does this immediately lead to the solution since $k$ is general? I can't see the link unfortunately Commented Apr 12, 2018 at 18:39

(Filling out the hint by hmakholm left over Monica to get this off the unanswered list.)

Let $$L$$ be the set of strings accepted by $$M$$, and suppose that $$L$$ is infinite. If $$\ell\le k\in\Bbb N$$, let

$$L_k=\{u\in L:|u|\ge k\}\,;$$

$$\Sigma$$ is finite and $$L$$ is infinite, so $$L$$ must contain arbitrarily long strings, and therefore $$L_k\ne\varnothing$$. Let $$m_k=\min\{|u|:u\in L_k\}$$, and fix $$u_k=\sigma_1\sigma_2\ldots\sigma_{m_k}\in L_k$$ such that $$|u_k|=m_k$$.

The input $$u_k$$ sends $$M$$ through a state sequence $$\langle s,q_1,q_2,\ldots,q_{m_k}\rangle$$, where $$q_{m_k}\in F$$. Suppose that $$m_k\ge k+\ell$$. $$M$$ has only $$\ell$$ states, so by the pigeonhole principle there are $$i,j\in\{k,k+1,\ldots,k+\ell\}$$ such that $$i and $$q_i=q_j$$. Clearly $$u_k'=\sigma_1\ldots\sigma_i\sigma_{j+1}\ldots\sigma_{m_k}$$ sends $$M$$ through the state sequence $$\langle s,\ldots,q_i,q_{j+1},\ldots,q_{m_k}\rangle$$, which terminates in the acceptor state $$q_{m_k}$$, so $$M$$ accepts $$u_k'$$. Moreover, $$|u_k'|\ge |u_k|-\ell=m_k-\ell\ge k$$, so $$u_k'\in L_k$$. This is impossible, since $$|u_k'|, so we must have $$m_k, and hence $$k\le|u_k|. The special case $$k=\ell$$ is the desired result.