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

Question

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.

Answer 1

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

Answer 2

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:

• Henning Bordihn, Markus Holzer, Martin Kutrib: Determination of finite automata accepting subregular languages, Theoretical Computer Science 410(35), 2009, pp. 3209-3222.

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

• M. Perles, M. O. Rabin and E. Shamir: The theory of definite automata, IEEE Trans. Comput. EC-12 (1963), pp. 233–243
• J. A. Brzozowski: Canonical regular expressions and minimal state graphs for definite events, in: J. Fox (Ed.), Mathematical Theory of Automata, in: MRI Symposia Series, vol. 12, Polytechnic Press of the Polytechnic Institute of Brooklyn, Brooklyn, NY, 1963, pp. 529–561.
• A. Ginzburg: About some properties of definite, reverse-definite and related automata, IEEE Trans. Comput. EC-15 (5) (1966), pp. 806–810
• Paz, A., Peleg, B. : Ultimate-definite and symmetric-definite events and automata, J. ACM 12 (1965), pp. 399–410

Answer 3

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

Answer 4

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

Answer 5

Such an automaton is called k–determined.

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