<p>It is possible. Consider all languages $L_1,\dots,L_m$ recognizable by automata with at most $n$ states.</p>

<p>Now to each $x=x_1\dots x_m\in\{0,1\}^m$ we associate a (possibly empty) language $$L_x=\bigcap_{1\leq i\leq m} L_i^{x_i},$$ where $L^0$ is the complement of $L$ and $L^1=L$.</p>

<p>Let $Y=\{x\in\{0,1\}^m~|~ L_x\neq\emptyset\}$.
For each $x\in Y$, we choose $\xi_x\in L_x$. This gives a finite family $\{\xi_x~|~x\in Y\}$, we show that this family satisfies the wanted property.</p>

<p>Take any $\eta\in X^{\mathbb N}$, and for each $i\leq m$ let $y_i$ be defined as $0$ if $\eta\notin L_i$ and $1$ if $\eta\in L_i$.
We have $y=y_1y_2\dots y_m\in Y$, since nonemptiness of $L_y$ is witnessed by $\eta$. We show that $\xi_{y}$ satisfies the condition. Indeed, for any $L$ recognized by an automaton with at most $n$ states, $L$ does not separate $\eta$ from $\xi_y$, by definition of $\xi_y$.</p>

<p>Notice that this family is optimal in size, since if some signature $x\in Y$ is not represented by some $\xi_x$, the property fails. Its size is at most doubly exponential in $n$.</p>

CC BY-SA 3.0
2017-05-05T10:08:40.637Z
2017-05-05T10:29:15.307Z
2017-05-05T10:29:15.307Z
Denis
<p>We consider acceptance by <a href="https://en.wikipedia.org/wiki/B%C3%BCchi_automaton" rel="nofollow noreferrer">Büchi automata</a>. Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi_1, \xi_2, \ldots, \xi_k \}$ of infinite words, such that for every other infinite word $\eta$ there exists some $\xi_i$ such that for every Büchi automaton $\mathcal A$ with
$$
 |L(\mathcal A) \cap \{\xi_i, \eta\}| = 1
$$ 
(i.e. the automaton separates both words: accepts one, but not the other) then $\mathcal A$ must have at least $n$ states?</p>

<p>Observation. One neccessary condition on the collection of infinite words $\{\xi_1, \ldots, \xi_k\}$: for a given $n$ we must have at least $2^{n-2}$ of them ($k \ge 2^{n-2}$), i.e. one for each prefix of length $n-2$, for otherwise if some prefix $u \in X^{n-2}$ is not among the finite collection, then we can separate $u1^{\omega}$ easily by an automaton having fewer then $n$ states from every word in $\xi_1, \ldots, \xi_k$, simply read upon the first position $i \le n-2$ where it differs from a given $\xi_j$ and then reject or accept according to the sign there, which could be achieved by a Büchi automaton with $i+2$ states.</p>

<p>But besides this observation, I do not see if this is possible?</p>

<p><em>Motivation</em>: If we define
$$
 d(\xi, \eta) = 1/2^n
$$
where $n := \min\{ |\mathcal A| \mid |L(\mathcal A) \cap \{\xi,\eta\}| = 1 \}$ for $\xi \ne \eta$, and $d(\xi,\xi) := 0$, then this gives a metric, and the above question asks if the resulting metric space is <a href="https://en.wikipedia.org/wiki/Totally_bounded_space" rel="nofollow noreferrer">totally bounded</a>.</p>

CC BY-SA 3.0
2017-05-05T00:40:43.053Z
Seems like an interesting question, but I'm curious as to the motivation...
Joshua Grochow
CC BY-SA 3.0
2017-05-05T13:11:12.997Z
@JoshuaGrochow I added a section on the motivation, it comes from metrics on infinite words.
StefanH
CC BY-SA 3.0
2017-05-05T15:06:46.293Z
Great, thanks - the motivation is also quite interesting.
Joshua Grochow
CC BY-SA 3.0
2017-05-05T15:48:39.007Z
@JoshuaGrochow To give more context, the metric space is related to a topology generated by all $\omega$-regular languages as base sets, I wrote about that in my master thesis, and it even resulted in a published paper: if you are interested you can find it here: http://www.sciencedirect.com/science/article/pii/S0304397516305175 or if you do not have access to TCS you can find a copy here: http://www.informatik.uni-halle.de/arbeitsgruppen/theorie/publikationen/cdmtcs/ [...]
StefanH
CC BY-SA 3.0
2017-05-05T15:48:44.470Z
[...] I recently just thought about that and gave a sequence showing non-completeness, and then started to think about an explicit proof for totally boundness. I would be very glad if I had aroused your interest far enough so you might take a look into the above links :)
StefanH
<fl.formal-languages><automata-theory>
Giving a finite collection of infinite words "complex" enough with respect to automata measure
StefanH
# Giving a finite collection of infinite words "complex" enough with respect to automata measure

(Asked by: username_0 on 2017-05-04)

We consider acceptance by [Büchi automata](https://en.wikipedia.org/wiki/B%C3%BCchi_automaton). Let $X = \{0,1\}$ and $X^{\mathbb N}$ the set of all infinite sequences. Then for each $n$ do we have a finite collection $\{ \xi\_1, \xi\_2, \ldots, \xi\_k \}$ of infinite words, such that for every other infinite word $\eta$ there exists some $\xi\_i$ such that for every Büchi automaton $\mathcal A$ with
$$
|L(\mathcal A) \cap \{\xi\_i, \eta\}| = 1
$$
(i.e. the automaton separates both words: accepts one, but not the other) then $\mathcal A$ must have at least $n$ states?

Observation. One neccessary condition on the collection of infinite words $\{\xi\_1, \ldots, \xi\_k\}$: for a given $n$ we must have at least $2^{n-2}$ of them ($k \ge 2^{n-2}$), i.e. one for each prefix of length $n-2$, for otherwise if some prefix $u \in X^{n-2}$ is not among the finite collection, then we can separate $u1^{\omega}$ easily by an automaton having fewer then $n$ states from every word in $\xi\_1, \ldots, \xi\_k$, simply read upon the first position $i \le n-2$ where it differs from a given $\xi\_j$ and then reject or accept according to the sign there, which could be achieved by a Büchi automaton with $i+2$ states.

But besides this observation, I do not see if this is possible?

*Motivation*: If we define
$$
d(\xi, \eta) = 1/2^n
$$
where $n := \min\{ |\mathcal A| \mid |L(\mathcal A) \cap \{\xi,\eta\}| = 1 \}$ for $\xi \ne \eta$, and $d(\xi,\xi) := 0$, then this gives a metric, and the above question asks if the resulting metric space is [totally bounded](https://en.wikipedia.org/wiki/Totally_bounded_space).

**Tags:** fl.formal-languages, automata-theory
> **Comments:**
> **username_1**: Seems like an interesting question, but I'm curious as to the motivation...  
> **username_0**: @JoshuaGrochow I added a section on the motivation, it comes from metrics on infinite words.  
> **username_1**: Great, thanks - the motivation is also quite interesting.  
> **username_0**: @JoshuaGrochow To give more context, the metric space is related to a topology generated by all $\omega$-regular languages as base sets, I wrote about that in my master thesis, and it even resulted in a published paper: if you are interested you can find it here: http://www.sciencedirect.com/science/article/pii/S0304397516305175 or if you do not have access to TCS you can find a copy here: http://www.informatik.uni-halle.de/arbeitsgruppen/theorie/publikationen/cdmtcs/ [...]  
> **username_0**: [...] I recently just thought about that and gave a sequence showing non-completeness, and then started to think about an explicit proof for totally boundness. I would be very glad if I had aroused your interest far enough so you might take a look into the above links :)  

---

## 1 answers

### Answer by username_2 on 2017-05-05. Score: 3 | Accepted answer

It is possible. Consider all languages $L\_1,\dots,L\_m$ recognizable by automata with at most $n$ states.

Now to each $x=x\_1\dots x\_m\in\{0,1\}^m$ we associate a (possibly empty) language $$L\_x=\bigcap\_{1\leq i\leq m} L\_i^{x\_i},$$ where $L^0$ is the complement of $L$ and $L^1=L$.

Let $Y=\{x\in\{0,1\}^m~|~ L\_x\neq\emptyset\}$.
For each $x\in Y$, we choose $\xi\_x\in L\_x$. This gives a finite family $\{\xi\_x~|~x\in Y\}$, we show that this family satisfies the wanted property.

Take any $\eta\in X^{\mathbb N}$, and for each $i\leq m$ let $y\_i$ be defined as $0$ if $\eta\notin L\_i$ and $1$ if $\eta\in L\_i$.
We have $y=y\_1y\_2\dots y\_m\in Y$, since nonemptiness of $L\_y$ is witnessed by $\eta$. We show that $\xi\_{y}$ satisfies the condition. Indeed, for any $L$ recognized by an automaton with at most $n$ states, $L$ does not separate $\eta$ from $\xi\_y$, by definition of $\xi\_y$.

Notice that this family is optimal in size, since if some signature $x\in Y$ is not represented by some $\xi\_x$, the property fails. Its size is at most doubly exponential in $n$.


---

