0
$\begingroup$

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?

$\endgroup$
5
  • $\begingroup$ 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). $\endgroup$ Commented Apr 12, 2018 at 18:10
  • $\begingroup$ 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$? $\endgroup$ Commented Apr 12, 2018 at 18:18
  • 1
    $\begingroup$ @StevenStadnicki: $w'=w$ is not necessarily a solution, because it is not assumed that $|w|<2l$. $\endgroup$ Commented Apr 12, 2018 at 18:19
  • $\begingroup$ Ahhh, I missed that. That makes good sense, thank you. $\endgroup$ Commented Apr 12, 2018 at 18:23
  • $\begingroup$ 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 $\endgroup$ Commented Apr 12, 2018 at 18:39

1 Answer 1

1
$\begingroup$

(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<j$ 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'|<m_k$, so we must have $m_k<k+\ell$, and hence $k\le|u_k|<k+\ell$. The special case $k=\ell$ is the desired result.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .