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 bs, 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.

Advertisements

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.
This entry was posted in academia, automata, geek, logic and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s