## Fun with Limit languages

Given an alphabet $\Sigma$ the set of all finite words over $\Sigma$ is denoted by $\Sigma^{*}$. The set of all infinite words over $\Sigma$ is denoted by $\Sigma^{\omega}$.

For any infinite word $\sigma$ let ${\it pref}(\sigma)$ denote the set of all prefixes of $\sigma$.

For a language $L \subseteq \Sigma^{*}$, we define the Limit Language of $L$ to be the subset of $\Sigma^{\omega}$ defined as $\hat{L} = \{\sigma | {\it pref}(\sigma) \cap L \text{ is an infinite set} \}$

Thus for each infinite word $\sigma$ in $L^{'}$, there is a totally ordered (with respect to the prefix ordering) infinite subset $S_{\sigma}$ of $L$.

Let us look at an infinite language $L^{'}$ over the alphabet $\Sigma = \{a, b\}$ where $L^{'} = \{\sigma | \sigma \text{ has finitely many b's} \}$

The question we are interested in is , can this $L^{'}$ be the limit language of some language $L$?

For now, let us assume that there is such a language $L \subseteq \Sigma^{*}$ whose limit language is $L^{'}$. Following the notation set up earlier,  $L^{'} = \hat{L}$.

Note that any word in $L^{'}$ can be viewed as some finite word over $\Sigma$ suffixed with infinite number of $a$‘s. And so, we can write $L^{'} = \Sigma^{*}a^{\omega}$.
It follows that for every $x \in \Sigma^{*}$, we have $xa^{\omega} \in L^{'}$. Since $L^{'}$ is also a limit language, there are infinitely many prefixes of $xa^{\omega}$ in $L$. This implies that we can always find an integer $n$ such that $xa^{n} \in L$.

Using this principle, we see that if $x=b$, then we can find a $n_0$ such that $ba^{n_0} \in L$. Now for $x = ba^{n_0} b$ we can find a $n_1$ such that $ba^{n_0} ba^{n_1} \in L$. We can similarly find $n_3, n_4, n_5, \ldots$ such that each prefix of the form $ba^{n_0} ba^{n_1} \ldots ba^{n_i}$  of the infinite string $\sigma^{'} = ba^{n_0} ba^{n_1}ba^{n_2}ba^{n_3} \ldots$ is in $L$. Thus infinitely many prefixes of $\sigma^{'}$ are in $L$.

[The notation setup below is only to satisfy my urge to make the aforementioned argument slightly more formal. And in the process make it unreadable. It can be safely skipped :P]

For every $x \in \Sigma^{*}$, define
$\mathbf{GoodSuffix}(x) = a^{n}$ where $n$ is the smallest natural number such that $xa^{n} \in L$

Let

• $y_0 = b$
• $z_i = \mathbf{GoodSuffix}(y_i)$ and
• $y_{i+1} = y_i z_i b$.

Now consider the infinite string $\sigma^{'} = b z_0 b z_1 b z_2 \ldots$

We note that $y_i z_i \in {\it pref}(\sigma^{'})$ $\forall i \in \mathbb{N}$
By construction, $y_i z_i \in L, \forall i \in \mathbb{N}$
Hence ${\it pref}(\sigma^{'}) \cap L$ is an infinite set.

The $\sigma^{'}$ thus constructed is in $\hat{L}$. Since $\sigma^{'}$ has infinitely many $b$s, it is not in $L^{'}$. But this implies that $L^{'} \ne \hat{L}$ contradicting our assumption.

Since $L$ is any arbitrary language, $L^{'}$ cannot be the limit language for any $L \subseteq \Sigma^{*}$.

In a subsequent post, we shall see how this particular set $L^{'}$ acts as an evidence in distinguishing between a particular class of Non-Deterministic Automata over infinite words from the corresponding class of Deterministic Automata over infinite words.