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
Now consider the infinite string
We note that
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.