patternMinor
Infinite non-regular decompositions of regular languages
Viewed 0 times
infinitenonlanguagesregulardecompositions
Problem
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
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.
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
- $L_i \cap L_j = \emptyset$ whenever $i \neq j$
- $\bigcup_{i \in \mathbb{N}} L_i = L$
- $\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.
Solution
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.
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.
Context
StackExchange Computer Science Q#28023, answer score: 3
Revisions (0)
No revisions yet.