Infinite non-regular decompositions of regular languages

Question

The title pretty much says it: I'm interested in examples of infinite families of non-regular, pairwise disjoint languages whose union is regular. When is this the case?

Or, from a different perspective: Given some regular language $L$, I want to find a family languages $(L_i)_{i \in \mathbb{N}}$ such that

1. $L_i \cap L_j = \emptyset$ whenever $i \neq j$
2. $\bigcup_{i \in \mathbb{N}} L_i = L$
3. $\forall i \in \mathbb{N}: L_i \notin \mathsf{REG}$

More specifically: When is such a decomposition possible (clearly, not every regular language is decomposable in this way, e.g. finite languages)?

A class of (motivating) examples is the following: Given some congruence relation $\sim$ on $\Sigma^\ast$ such that the elements of $\Sigma^\ast /\sim$ are non-regular, every language saturated by $\sim$ admits a decomposition as above. One such congruence is the congruence $\sim_R$ generated by the identities $\{a^2 \sim_R \lambda ~:~ a \in \Sigma\}$, assuming $|\Sigma| > 1$. An example for a language saturated by $\sim_R$ is the language consisting of words containing an even (odd) number of occurrences of some symbol from $\Sigma$. More generally, languages accepted by complete deterministic automata with symmetric transition relations (that is, $q\cdot aa = q$ for all states $q$ and symbols $a$) are saturated by $\sim_R$.

However, I fail to see some general criterion for a language being decomposable in this way.

Answer 1

We show below that every infinite language can be partitioned into two non-regular languages. Using this, let us show that we can partition every infinite language $L$ into infinitely many non-regular languages. The construction goes as follows.

Choose an arbitrary ordering of $\Sigma^*$. Let $R_0 := L$. We will maintain the invariant that $R_0$ is infinite. Given $R_i$, partition it into two non-regular languages. Let $L_{i+1}$ be the part with the smaller minimal word, and let $R_{i+1} = R_i \setminus L_{i+1}$. Note that $R_{i+1}$ is non-regular, and so infinite.

By construction, all $L_i$ are non-regular, and they are disjoint. Also, the $i$th word in the ordering is contained in $L_1 \cup \cdots \cup L_i$ by construction, and so $\bigcup_{i=1}^\infty L_i = L$.

It remains to show that every infinite language can be partitioned into two non-regular languages. Recall that if a language is regular, then the set of lengths of words in the language is eventually periodic, and in particular, has the bounded gap property (the gap between adjacent elements is bounded). Therefore it suffices to show that every infinite subset of $\mathbb{N}$ can be partitioned into two subsets without the bounded gap property.

We imagine the infinite subset as an increasing sequence which is presented to us element by element. We will drop the elements into two buckets $A,B$ which will not have the bounded gap property. The construction proceeds in stages. In stage $2t$, we put the first element $x$ into $A$, and then put all elements into $B$ until an element $y \geq x + t$ shows up. We put $y$ into $A$, and move to stage $2t+1$, in which we proceed similarly, with the roles of $A$ and $B$ reversed.

Answer 2

Your intuition does not match mine, I think this is possible for every initial (infinite) regular language. My idea is that every infinite language has an (infinite) non-regular subset, such that the complement is also infinite. You then can repeatedly find the next language which together form a non-regular decomposition.

How to prove the basic observation? Just set half of the words apart (for the complement, the set of words is countable, so order them). In the remaining words you choose a subset that has ever greater sizes, not growing linearly but at least say exponential. Such a subset cannot be regular.

How do we obtain a decomposition that way: we might omit a string in each step. This is dealt by taking the shortest remaining string in the next language. That choice does not influence any regularity.