<p>Adding to Mikhail Rudoy's very good answer: the languages of the form <span class="math-container">$\Sigma^*\cdot X \cup Y$</span> are known under the name <em>definite languages</em> (resp. <em>definite events</em> in the lingo of the 1960s). The following paper contains a nice diagram comparing the definite languages to many other &quot;subregular&quot; language classes:</p>
<ul>
<li>Henning Bordihn, Markus Holzer, Martin Kutrib: <a href="https://doi.org/10.1016/j.tcs.2009.05.019" rel="noreferrer">Determination of finite automata accepting subregular languages</a>, Theoretical Computer Science 410(35), 2009, pp. 3209-3222.</li>
</ul>
<p>As mentioned in that paper, the early automata theory literature features quite a few results concerning definite languages and related classes:</p>
<ul>
<li>M. Perles, M. O. Rabin and E. Shamir: <a href="https://doi.org:10.1109/PGEC.1963.263534" rel="noreferrer">The theory of definite automata</a>, IEEE Trans. Comput. EC-12 (1963), pp. 233–243</li>
<li>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.</li>
<li>A. Ginzburg: <a href="https://doi.org/10.1109/PGEC.1966.264264" rel="noreferrer">About some properties of definite, reverse-definite and related automata</a>, IEEE Trans. Comput. EC-15 (5) (1966), pp. 806–810</li>
<li>Paz, A., Peleg, B. : <a href="https://doi.org/10.1145/321281.321292" rel="noreferrer">Ultimate-definite and symmetric-definite events and automata</a>, J. ACM 12 (1965), pp. 399–410</li>
</ul>

CC BY-SA 4.0
2024-08-05T10:28:20.407Z
Wow these references are super interesting!
Nicola Gigante
CC BY-SA 4.0
2024-08-04T16:36:57.983Z
2024-08-05T11:40:29.467Z
2024-08-05T11:40:29.467Z
Hermann Gruber
<p>This is very reminiscent of <a href="https://en.wikipedia.org/wiki/Synchronizing_word" rel="nofollow noreferrer">synchronizing words</a>. However in your case all words of length more than <span class="math-container">$k$</span> are synchronizing.</p>

CC BY-SA 4.0
2024-08-01T16:13:44.147Z
That's a useful pointer!
Nicola Gigante
CC BY-SA 4.0
2024-08-01T16:10:46.467Z
2024-08-01T16:10:46.467Z
ULechine
<p>Such an automaton is called k–determined.</p>
<p>It is very closely related to foldings of de Bruijn graphs.</p>

CC BY-SA 4.0
2024-08-02T16:57:25.537Z
2024-08-02T18:27:33.247Z
2024-08-02T18:27:33.247Z
1001
<p><strong>Edit: following an edit to the question, what follows is not correct -- it assumes that the state reached is the same for all words.</strong></p>
<p>I think that the automata that obey your condition recognize precisely the languages that are either finite or cofinite.</p>
<p>For one direction, let <span class="math-container">$A$</span> be such an automaton. We know that, for any word <span class="math-container">$w$</span> with <span class="math-container">$|w|&gt;n$</span>, reading <span class="math-container">$w$</span> leads us to one state <span class="math-container">$q$</span>. Hence, the language of <span class="math-container">$A$</span> is finite if <span class="math-container">$q$</span> is not accepting (only words of length <span class="math-container">$\leq n$</span> can be accepted, hence finitely many), and cofinite if <span class="math-container">$q$</span> is accepting (only words of length <span class="math-container">$\leq n$</span> can be rejected, hence finitely many).</p>
<p>Conversely, let <span class="math-container">$L$</span> be a finite language, letting <span class="math-container">$n$</span> be greater than the length of the longest word of <span class="math-container">$L$</span>, we can build a DFA for <span class="math-container">$L$</span> where any word longer than <span class="math-container">$n$</span> gets mapped to a rejecting sink state. A similar argument works for cofinite languages <span class="math-container">$L$</span>: letting <span class="math-container">$n$</span> be greater than the length of the longest word which is not in <span class="math-container">$L$</span>, we can build a DFA for <span class="math-container">$L$</span> where any word longer than <span class="math-container">$n$</span> gets mapped to an accepting sink state. (In fact, for <span class="math-container">$L$</span> finite or cofinite, your property will in particular be obeyed by the minimal DFA for <span class="math-container">$L$</span>.)</p>

CC BY-SA 4.0
2024-08-01T14:48:27.893Z
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.
Nicola Gigante
CC BY-SA 4.0
2024-08-01T14:04:53.870Z
2024-08-02T14:03:39.947Z
2024-08-02T14:03:39.947Z
Antoine Amarilli 'a3nm'
<p>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.</p>
<p>An automaton of this form must accept a language of the form <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>, where <span class="math-container">$X$</span> is a finite set of strings of the same length <span class="math-container">$k$</span>, and <span class="math-container">$Y$</span> is a finite set of strings each of length less than <span class="math-container">$k$</span>. In other words, for strings of length at least <span class="math-container">$k$</span>, the automaton must accept exactly those strings that end in a string in <span class="math-container">$X$</span>, while for strings of length at most <span class="math-container">$k$</span>, the automaton must accept exactly those strings in <span class="math-container">$Y$</span>.</p>
<p>On the other hand, if we have a set <span class="math-container">$X$</span> of strings of the same length <span class="math-container">$k$</span>, and another set <span class="math-container">$Y$</span> of strings each of length less than <span class="math-container">$k$</span>, then we can construct an automaton matching your constraints that accepts exactly the language <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>.</p>
<h2>proofs</h2>
<p>Let's prove these two claims one at a time. First, consider an automaton <span class="math-container">$A$</span> of your form with an associated value of <span class="math-container">$k$</span>. Let <span class="math-container">$Y$</span> be the set of strings of length less than <span class="math-container">$k$</span> that are accepted by <span class="math-container">$A$</span>. And let <span class="math-container">$X$</span> be the set of strings <span class="math-container">$w$</span> of length exactly <span class="math-container">$k$</span> such that <span class="math-container">$q_w$</span> is an accepting state. I claim that the language of the automaton <span class="math-container">$L(A)$</span> is then <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>. 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 <span class="math-container">$k$</span> and not:</p>
<ul>
<li>If <span class="math-container">$w$</span> is a string of length less than <span class="math-container">$k$</span> and is in <span class="math-container">$L(A)$</span>, then by definition of <span class="math-container">$Y$</span>, <span class="math-container">$w$</span> is in <span class="math-container">$Y$</span>, and so <span class="math-container">$w$</span> is also in <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>.</li>
<li>If <span class="math-container">$w$</span> is a string of length less than <span class="math-container">$k$</span> and is not in <span class="math-container">$L(A)$</span>, then by definition of <span class="math-container">$Y$</span>, <span class="math-container">$w$</span> is not in <span class="math-container">$Y$</span>. Also, <span class="math-container">$(\Sigma^*\cdot X)$</span> contains only strings of length at least <span class="math-container">$k$</span>, so <span class="math-container">$w$</span> is also not in <span class="math-container">$(\Sigma^*\cdot X)$</span>. As a result, <span class="math-container">$w$</span> is not in <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>.</li>
<li>If <span class="math-container">$w$</span> is a string of length at least <span class="math-container">$k$</span> and is in <span class="math-container">$L(A)$</span>, then let <span class="math-container">$w'$</span> be the suffix of <span class="math-container">$w$</span> of length <span class="math-container">$k$</span>. We know that no matter the start state, running <span class="math-container">$A$</span> on input <span class="math-container">$w'$</span> will lead to state <span class="math-container">$q_{w'}$</span>. Therefore, running <span class="math-container">$A$</span> on <span class="math-container">$w$</span> must end at state <span class="math-container">$q_{w'}$</span>, since the last <span class="math-container">$k$</span> steps of that execution are exactly the process of running <span class="math-container">$A$</span> on <span class="math-container">$w'$</span> from some starting state. Since <span class="math-container">$A$</span> accepts <span class="math-container">$w$</span>, we can conclude that <span class="math-container">$q_{w'}$</span> is an accepting state. Therefore, <span class="math-container">$w'$</span> must be in <span class="math-container">$X$</span> (by the definition of <span class="math-container">$X$</span>), and so <span class="math-container">$w$</span> must be in <span class="math-container">$(\Sigma^*\cdot X)$</span>. As a result, we see that <span class="math-container">$w$</span> is in <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>.</li>
<li>If <span class="math-container">$w$</span> is a string of length at least <span class="math-container">$k$</span> and is not in <span class="math-container">$L(A)$</span>, then let <span class="math-container">$w'$</span> be the suffix of <span class="math-container">$w$</span> of length <span class="math-container">$k$</span> just like in the previous case. As before, running <span class="math-container">$A$</span> on <span class="math-container">$w$</span> must end at state <span class="math-container">$q_{w'}$</span>, so since <span class="math-container">$A$</span> rejects <span class="math-container">$w$</span>, we can conclude that <span class="math-container">$q_{w'}$</span> is not an accepting state. Therefore, <span class="math-container">$w'$</span> must not be in <span class="math-container">$X$</span> (by the definition of <span class="math-container">$X$</span>), and so <span class="math-container">$w$</span> must not be in <span class="math-container">$(\Sigma^*\cdot X)$</span>. We also know that <span class="math-container">$w$</span> is not in <span class="math-container">$Y$</span> since <span class="math-container">$w$</span> has length at least <span class="math-container">$k$</span>, while strings in <span class="math-container">$Y$</span> have length less than <span class="math-container">$k$</span>. Putting this together, we see that <span class="math-container">$w$</span> is not in <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>.</li>
</ul>
<p>All of this casework has shown that a string <span class="math-container">$w$</span> is in <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span> exactly when it is in <span class="math-container">$L(A)$</span>, and therefore that <span class="math-container">$L(A)=(\Sigma^*\cdot X) \cup Y$</span>.</p>
<p>Now, suppose we have a set <span class="math-container">$X$</span> of strings of the same length <span class="math-container">$k$</span>, and another set <span class="math-container">$Y$</span> of strings each of length less than <span class="math-container">$k$</span>. We will construct an automaton matching your constraints that accepts exactly the language <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>. This automaton will contain a state for every string of length at most <span class="math-container">$k$</span>, and the transitions will be such that at all times, the state is the longest suffix of the input so far of length <span class="math-container">$\le k$</span>. This means the DFA will start at the empty string state, on input <span class="math-container">$x$</span>, a state <span class="math-container">$w$</span> with <span class="math-container">$|w| &lt; k$</span> will transition to state <span class="math-container">$wx$</span>, and on input <span class="math-container">$x$</span>, a state <span class="math-container">$aw$</span> with <span class="math-container">$|a|=1$</span> and <span class="math-container">$|w| = k-1$</span> will transition to the state <span class="math-container">$wx$</span>. Finally, the accept states of this DFA will be exactly the strings in <span class="math-container">$X$</span> and <span class="math-container">$Y$</span>.</p>
<p>It's pretty straightforward to see that the constructed DFA has language <span class="math-container">$(\Sigma^*\cdot X) \cup Y$</span>. It is also an automaton matching your constraints since for every <span class="math-container">$w$</span> of length at least <span class="math-container">$k$</span>, if you let <span class="math-container">$w'$</span> be the length <span class="math-container">$k$</span> suffix of <span class="math-container">$w$</span>, running the automaton on <span class="math-container">$w$</span> from any state will put the DFA into state <span class="math-container">$w'$</span>. In other words, <span class="math-container">$q_w=w'$</span>.</p>

CC BY-SA 4.0
2024-08-02T07:08:34.940Z
This looks correct to me. Very nice!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2024-08-02T12:21:13.067Z
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.
Emil Jeřábek
CC BY-SA 4.0
2024-08-03T06:41:29.253Z
That’s really nice! Then I think I’ll need a weaker hypothesis for what I’m doing. Thanks!
Nicola Gigante
CC BY-SA 4.0
2024-08-02T03:34:21.280Z
2024-08-02T03:34:21.280Z
Mikhail Rudoy
<p>Suppose there is a deterministic finite automaton (DFA) <span class="math-container">$A$</span> for which there is a <span class="math-container">$k&gt;0$</span> such that, for all words <span class="math-container">$w$</span> longer than <span class="math-container">$k$</span>, there is a state <span class="math-container">$q_w$</span> such that reading <span class="math-container">$w$</span> starting from any other state of <span class="math-container">$A$</span> will reach <span class="math-container">$q_w$</span>.</p>
<p>In other words, the &quot;effect&quot; of reading <span class="math-container">$w$</span> is the same no matter the prefix, but only if <span class="math-container">$w$</span> is long enough.</p>
<p>Is there a standard name for automata of this kind and what is known about them?</p>
<p><strong>Edit</strong>: clarified that there is one state for each long-enough word and not a single state for all the long words.</p>

<reference-request><automata-theory>
Automata reaching the same state when reading the same word long enough
Nicola Gigante
# Automata reaching the same state when reading the same word long enough

(Asked by: username_0 on 2024-08-01)

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.

**Tags:** reference-request, automata-theory


---

## 5 answers

### Answer by username_5 on 2024-08-02. Score: 11 | Accepted answer

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

> **Comments:**
> **username_4**: This looks correct to me. Very nice!  
> **username_6**: 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.  
> **username_0**: That’s really nice! Then I think I’ll need a weaker hypothesis for what I’m doing. Thanks!  

---

### Answer by username_1 on 2024-08-04. Score: 9

Adding to username_5'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](https://doi.org/10.1016/j.tcs.2009.05.019), 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](https://doi.org:10.1109/PGEC.1963.263534), 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](https://doi.org/10.1109/PGEC.1966.264264), IEEE Trans. Comput. EC-15 (5) (1966), pp. 806–810
* Paz, A., Peleg, B. : [Ultimate-definite and symmetric-definite events and automata](https://doi.org/10.1145/321281.321292), J. ACM 12 (1965), pp. 399–410

> **Comments:**
> **username_0**: Wow these references are super interesting!  

---

### Answer by username_2 on 2024-08-01. Score: 4

This is very reminiscent of [synchronizing words](https://en.wikipedia.org/wiki/Synchronizing_word). However in your case all words of length more than $k$ are synchronizing.

> **Comments:**
> **username_0**: That's a useful pointer!  

---

### Answer by username_3 on 2024-08-02. Score: 2

Such an automaton is called k–determined.

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


---

### Answer by username_4 on 2024-08-01. Score: 1

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

> **Comments:**
> **username_0**: 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.  

---

