DFA with $k$ states, words of length $k$

756 Views Asked by At

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.

1

There are 1 best solutions below

8
On BEST ANSWER

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