Given an alphabet the set of all finite words over is denoted by . The set of all infinite words over is denoted by .

For any infinite word let denote the set of all prefixes of .

For a language , we define the **Limit Language** of to be the subset of defined as

Thus for each infinite word in , there is a totally ordered (with respect to the prefix ordering) infinite subset of .

Let us look at an infinite language over the alphabet where

The question we are interested in is , can this be the limit language of some language ?

For now, let us assume that there is such a language whose limit language is . Following the notation set up earlier, .

Note that any word in can be viewed as some finite word over suffixed with infinite number of ‘s. And so, we can write .

It follows that for every , we have . Since is also a limit language, there are infinitely many prefixes of in . This implies that we can always find an integer such that .

Using this principle, we see that if , then we can find a such that . Now for we can find a such that . We can similarly find such that each prefix of the form of the infinite string is in . Thus infinitely many prefixes of are in .

[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 , define

where is the smallest natural number such that

Let

Now consider the infinite string

We note that

By construction,

Hence is an infinite set.

The thus constructed is in . Since has infinitely many s, it is not in . But this implies that contradicting our assumption.

Since is any arbitrary language, cannot be the limit language for any .

In a subsequent post, we shall see how this particular set 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.

### Like this:

Like Loading...

## About gautshen

A jack of many trades of which , Linux Kernel Programming puts food on the table. Also pursuing his PhD in the area Theoretical Computer Science at the Chennai Mathematical Institute.
Is an avid reader interested in the Hindu traditions and philosophy. Loves Bicycling and Good Music.
Name is Ranjal Gautham Shenoy.