0

Is this statement true?

If we have a DFA with $k$ states, and if $L(M) = L$ is infinite, then there is a word of length at least $k$ and at most $2k-1$.

Isn't this a trivial answer?

Take the DFA, then since $L$ is infinite, there is a word that visits all states of M exactly once, meaning that that word is of length $k$ exactly, thus satisfying that there is a word $w$ such that $k \leq |w| \leq 2k-1$

I am quite not sure of this, as what is the use of the fact that $L$ is infinite? Somewhat I think it relates to the pumping lemma.

TheNotMe
  • 4,841

1 Answers1

1

The statement to be proved should say that the word in question is in $L$. In any case, there need not be a word that visits each state of $M$ exactly once: $M$ may have states that aren’t reachable from the initial state, and even if all states are reachable, there may be no word that visits each of them exactly once.

The idea is that a word of length $n$ can visit at most $n+1$ different states, including the initial state. If $n\ge k$, then of course $n+1$ is greater than the number of states, and the word must visit some state twice. Let $w$ be a word of length $n\ge k$, and let $q$ be a state that $w$ visits twice. Then we can decompose $w$ as $w=xyz$, where $x$ takes $M$ to state $q$, $y$ takes $M$ to $q$ the second time, $z$ is the rest of $w$, and of course $|y|\ge 1$.

Now let’s suppose further that $w\in L$ and that $q_f$ is the acceptor state to which $w$ drives $M$. If $q_0$ is the initial state of $M$, this means that $x$ drives $M$ from $q_0$ to $q$, $y$ drives $M$ from $q$ back to $q$, and $z$ drives $M$ from $q$ to $q_f$. The shorter word $xz$ would drive $M$ from $q_0$ to $q$ to $q_f$ and would also be accepted. The longer word $xy^2z$ would drive $M$ from $q_0$ to $q$, twice around some loop of states to $q$ again, and on to $q_f$, so it would also be accepted. In fact, $xy^mz$ would be accepted for every integer $m\ge 0$: it would drive $M$ from $q_0$ to $q$, then $m$ times around a loop back to $q$, and finally from $q$ to the acceptor state $q_f$. (And yes, this proves the pumping lemma for regular languages: the pumping length here is $k$.)

If $L$ is infinite, then it certainly contains some word $w$ whose length is at least $k$. In fact, we can choose $w$ to be as short as possible, meaning that if $u\in L$ and $|u|<|w|$, then $|u|<k$. Use the result of the preceding paragraph to show that $k\le|w|<2k$.

Brian M. Scott
  • 616,228
  • Just to clarify, saying that there certainly is a word $w$ whose length is at least $k$ simply derives from the fact that $L$ is infinite, correct? – TheNotMe Dec 01 '13 at 07:58
  • @TheNotMe: Yes, that’s right. – Brian M. Scott Dec 01 '13 at 08:01
  • But what is the formal explanation of this? – TheNotMe Dec 01 '13 at 08:03
  • 1
    @TheNotMe: Suppose that $|\Sigma|=n$, where $\Sigma$ is the alphabet of symbols. For any non-negative integer $\ell$ there are $n^ell$ words of length $\ell$. Thus, there are at most $$n^0+n^1+n^2+\ldots+n^{k-1}=\frac{n^k-1}{k-1}$$ words of length less than $k$. As long as $L$ has more words than that — and if it’s infinite, it certainly does! — then it must contain a word of length $\ge k$. – Brian M. Scott Dec 01 '13 at 08:06
  • Thank you. And in the last paragraph, what made you so sure that there indeed is a word $u$ of length less than $k$? – TheNotMe Dec 01 '13 at 08:09
  • @TheNotMe: That’s not what it says. Let $L'={v\in L:|v|\ge k}$, let $m$ be the smallest length of any word in $L'$, and choose $w\in L'$ such that $|w|=m$. What that last paragraph says is that if $u\in L$ and $|u|<|w|$, then $u\notin L_0$ (since $u$ is shorter than the minimum length of anything in $L_0$), so $|u|<k$. – Brian M. Scott Dec 01 '13 at 08:13
  • By $L_{0}$ you mean $L^{'}$, of course? – TheNotMe Dec 01 '13 at 08:35
  • @TheNotMe: I do indeed. – Brian M. Scott Dec 01 '13 at 08:45