# Automata reaching the same state when reading the same word long enough

Suppose there is a deterministic finite automaton (DFA) $$A$$ for which there is a $$k>0$$ such that, for all words $$w$$ longer than $$k$$, there is a state $$q_w$$ such that reading $$w$$ starting from any other state of $$A$$ will reach $$q_w$$.

In other words, the "effect" of reading $$w$$ is the same no matter the prefix, but only if $$w$$ is long enough.

Is there a standard name for automata of this kind and what is known about them?

Edit: clarified that there is one state for each long-enough word and not a single state for all the long words.

I don't have any references to point you towards for this kind of automaton, but I can tell you exactly what languages can be recognized by this type of automaton.

An automaton of this form must accept a language of the form $$(\Sigma^*\cdot X) \cup Y$$, where $$X$$ is a finite set of strings of the same length $$k$$, and $$Y$$ is a finite set of strings each of length less than $$k$$. In other words, for strings of length at least $$k$$, the automaton must accept exactly those strings that end in a string in $$X$$, while for strings of length at most $$k$$, the automaton must accept exactly those strings in $$Y$$.

On the other hand, if we have a set $$X$$ of strings of the same length $$k$$, and another set $$Y$$ of strings each of length less than $$k$$, then we can construct an automaton matching your constraints that accepts exactly the language $$(\Sigma^*\cdot X) \cup Y$$.

## proofs

Let's prove these two claims one at a time. First, consider an automaton $$A$$ of your form with an associated value of $$k$$. Let $$Y$$ be the set of strings of length less than $$k$$ that are accepted by $$A$$. And let $$X$$ be the set of strings $$w$$ of length exactly $$k$$ such that $$q_w$$ is an accepting state. I claim that the language of the automaton $$L(A)$$ is then $$(\Sigma^*\cdot X) \cup Y$$. To prove this, we can consider four cases by splitting all strings into those accepted by the automaton and not and also those of length less than $$k$$ and not:

• If $$w$$ is a string of length less than $$k$$ and is in $$L(A)$$, then by definition of $$Y$$, $$w$$ is in $$Y$$, and so $$w$$ is also in $$(\Sigma^*\cdot X) \cup Y$$.
• If $$w$$ is a string of length less than $$k$$ and is not in $$L(A)$$, then by definition of $$Y$$, $$w$$ is not in $$Y$$. Also, $$(\Sigma^*\cdot X)$$ contains only strings of length at least $$k$$, so $$w$$ is also not in $$(\Sigma^*\cdot X)$$. As a result, $$w$$ is not in $$(\Sigma^*\cdot X) \cup Y$$.
• If $$w$$ is a string of length at least $$k$$ and is in $$L(A)$$, then let $$w'$$ be the suffix of $$w$$ of length $$k$$. We know that no matter the start state, running $$A$$ on input $$w'$$ will lead to state $$q_{w'}$$. Therefore, running $$A$$ on $$w$$ must end at state $$q_{w'}$$, since the last $$k$$ steps of that execution are exactly the process of running $$A$$ on $$w'$$ from some starting state. Since $$A$$ accepts $$w$$, we can conclude that $$q_{w'}$$ is an accepting state. Therefore, $$w'$$ must be in $$X$$ (by the definition of $$X$$), and so $$w$$ must be in $$(\Sigma^*\cdot X)$$. As a result, we see that $$w$$ is in $$(\Sigma^*\cdot X) \cup Y$$.
• If $$w$$ is a string of length at least $$k$$ and is not in $$L(A)$$, then let $$w'$$ be the suffix of $$w$$ of length $$k$$ just like in the previous case. As before, running $$A$$ on $$w$$ must end at state $$q_{w'}$$, so since $$A$$ rejects $$w$$, we can conclude that $$q_{w'}$$ is not an accepting state. Therefore, $$w'$$ must not be in $$X$$ (by the definition of $$X$$), and so $$w$$ must not be in $$(\Sigma^*\cdot X)$$. We also know that $$w$$ is not in $$Y$$ since $$w$$ has length at least $$k$$, while strings in $$Y$$ have length less than $$k$$. Putting this together, we see that $$w$$ is not in $$(\Sigma^*\cdot X) \cup Y$$.

All of this casework has shown that a string $$w$$ is in $$(\Sigma^*\cdot X) \cup Y$$ exactly when it is in $$L(A)$$, and therefore that $$L(A)=(\Sigma^*\cdot X) \cup Y$$.

Now, suppose we have a set $$X$$ of strings of the same length $$k$$, and another set $$Y$$ of strings each of length less than $$k$$. We will construct an automaton matching your constraints that accepts exactly the language $$(\Sigma^*\cdot X) \cup Y$$. This automaton will contain a state for every string of length at most $$k$$, and the transitions will be such that at all times, the state is the longest suffix of the input so far of length $$\le k$$. This means the DFA will start at the empty string state, on input $$x$$, a state $$w$$ with $$|w| < k$$ will transition to state $$wx$$, and on input $$x$$, a state $$aw$$ with $$|a|=1$$ and $$|w| = k-1$$ will transition to the state $$wx$$. Finally, the accept states of this DFA will be exactly the strings in $$X$$ and $$Y$$.

It's pretty straightforward to see that the constructed DFA has language $$(\Sigma^*\cdot X) \cup Y$$. It is also an automaton matching your constraints since for every $$w$$ of length at least $$k$$, if you let $$w'$$ be the length $$k$$ suffix of $$w$$, running the automaton on $$w$$ from any state will put the DFA into state $$w'$$. In other words, $$q_w=w'$$.

• This looks correct to me. Very nice!
– a3nm
Commented Aug 2 at 7:08
• Another characterization is that a DFA such that all states are reachable has the property in the OP iff it is a quotient of an automaton on $\Sigma^{\le k}$ described in the penultimate paragraph. Commented Aug 2 at 12:21
• That’s really nice! Then I think I’ll need a weaker hypothesis for what I’m doing. Thanks! Commented Aug 3 at 6:41

Adding to Mikhail Rudoy's very good answer: the languages of the form $$\Sigma^*\cdot X \cup Y$$ are known under the name definite languages (resp. definite events in the lingo of the 1960s). The following paper contains a nice diagram comparing the definite languages to many other "subregular" language classes:

As mentioned in that paper, the early automata theory literature features quite a few results concerning definite languages and related classes:

• Wow these references are super interesting! Commented Aug 5 at 10:28

This is very reminiscent of synchronizing words. However in your case all words of length more than $$k$$ are synchronizing.

• That's a useful pointer! Commented Aug 1 at 16:13

Edit: following an edit to the question, what follows is not correct -- it assumes that the state reached is the same for all words.

I think that the automata that obey your condition recognize precisely the languages that are either finite or cofinite.

For one direction, let $$A$$ be such an automaton. We know that, for any word $$w$$ with $$|w|>n$$, reading $$w$$ leads us to one state $$q$$. Hence, the language of $$A$$ is finite if $$q$$ is not accepting (only words of length $$\leq n$$ can be accepted, hence finitely many), and cofinite if $$q$$ is accepting (only words of length $$\leq n$$ can be rejected, hence finitely many).

Conversely, let $$L$$ be a finite language, letting $$n$$ be greater than the length of the longest word of $$L$$, we can build a DFA for $$L$$ where any word longer than $$n$$ gets mapped to a rejecting sink state. A similar argument works for cofinite languages $$L$$: letting $$n$$ be greater than the length of the longest word which is not in $$L$$, we can build a DFA for $$L$$ where any word longer than $$n$$ gets mapped to an accepting sink state. (In fact, for $$L$$ finite or cofinite, your property will in particular be obeyed by the minimal DFA for $$L$$.)

• I'm sorry, I think the question was ambigue. What I meant is that for each word long enough there is a state where you end up when you read the same word, not that the state is the same for all long words. I'll edit the question. Commented Aug 1 at 14:48

Such an automaton is called k–determined.

It is very closely related to foldings of de Bruijn graphs.