<p>Interesting, I was recently writing a blog post on a related topic.</p>
<p>Namely, you have probably seen the term <em>rational languages</em> used for regular languages. This is because the generating function (g.f.) of a regular language is a rational function.¹
The generating function of the set <span class="math-container">$A$</span> is the formal series <span class="math-container">$$f_A(X) = \sum_{n \ge 0} a_n X^n,$$</span>
where <span class="math-container">$a_n = |A\cap\Sigma^n|$</span> is the number of word of length <span class="math-container">$n$</span> in <span class="math-container">$A$</span>.
A rational function is a function <span class="math-container">$f$</span> such that there exists polynomials <span class="math-container">$P$</span> and <span class="math-container">$Q$</span> such that <span class="math-container">$f(x) = P(X)/Q(X)$</span> over the domain of <span class="math-container">$f$</span>.</p>
<p>The proof goes like this:</p>
<ol>
<li>the g.f. of a finite language is a polynomial,</li>
<li>the g.f. of the union of two disjoint languages is the sum of the generating functions</li>
<li>under some condition of unambiguity, the g.f. of a concatenation is the product of the g.f.'s and</li>
<li>the g.f. of <span class="math-container">$A^*$</span> is  <span class="math-container">$1/(1-f_A)$</span> if the Kleene star is &quot;unambiguous&quot;.</li>
</ol>
<p>In points 3 and 4 here, unambiguous means that every word in the resulting language can be obtained in a unique manner using the operation. In that sense, a disjoint union is an unambiguous union.</p>
<p>One then proves that the class of languages obtained from finite languages and applying disjoint union, unambiguous concatenation, and unambiguous Kleene star is equal to regular languages. (I believe this step is basically Kleene's algorithm on a DFA)</p>
<p>See <a href="https://people.math.carleton.ca/%7Ebsteinbg/classes/automata2009/generatingfunctions.pdf" rel="nofollow noreferrer">these lecture notes</a> for full details.</p>
<p>So my answer to your question <strong>Has this fact been observed anywhere?</strong> is <strong>Yes</strong>, and it was also strengthened with an unambiguous version of the other two operations: concatenation and Kleene star.</p>
<hr />
<p>[1]: note, the converse is not true, the set of (even) palindromes is a counterexample.</p>

CC BY-SA 4.0
2023-02-28T22:12:25.077Z
This is absolutely to the point. I just thought of the old observation that state elimination transforms unambiguous finite automata into unambiguous regular expressions, and wanted to update my answer, then I read yours.
Hermann Gruber
CC BY-SA 4.0
2023-02-28T14:08:30.667Z
2023-02-28T14:13:49.153Z
2023-02-28T14:13:49.153Z
GBathie
<p>This question has indeed been studied: namely, from the perspective of representing regular languages as unions of so-called <em>regular components</em> that is, loop expressions of the form <span class="math-container">$uv^+w$</span>, and a finite set <span class="math-container">$F$</span> of words. Every regular language can be written as the (possibly infinite) disjoint union of regular components and a finite set. See also the references in the following paper:</p>
<p>Y.J. Liu: Regular component decomposition of regular languages, Theoretical Computer Science 299(1–3), 2003, pp. 743-749 <a href="https://doi.org/10.1016/S0304-3975(02)00064-6" rel="nofollow noreferrer">https://doi.org/10.1016/S0304-3975(02)00064-6</a></p>
<p>Also somewhat related, the state complexity of disjoint union as a language operation applied to deterministic finite automata was determined here:</p>
<p>Galina Jirásková, Alexander Okhotin: State complexity of unambiguous operations on finite automata, International Conference on Descriptional Complexity of Formal Systems (DCFS) 2018, Lecture Notes in Computer Science Vol. 10952, pp. 188–199 <a href="https://doi.org/10.1007/978-3-319-94631-3_16" rel="nofollow noreferrer">https://doi.org/10.1007/978-3-319-94631-3_16</a></p>

CC BY-SA 4.0
2023-02-28T11:10:50.157Z
In case someone is as confused as I was: every regular language can be written as a *possibly infinite* disjoint union of regular components and a finite set.
Emil Jeřábek
CC BY-SA 4.0
2023-02-28T12:26:27.307Z
Interesting pointers, thanks!
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-28T22:15:44.090Z
@EmilJeřábek thanks, I updated my answer!
Hermann Gruber
CC BY-SA 4.0
2023-02-28T07:53:47.987Z
2023-02-28T22:14:51.070Z
2023-02-28T22:14:51.070Z
Hermann Gruber
<p><a href="https://en.wikipedia.org/wiki/Regular_language" rel="noreferrer">Regular languages</a> are typically defined using the operations of union, concatenation, and Kleene star. Likewise, there are restricted classes of regular languages defined via similar operations, for instance <a href="https://en.wikipedia.org/wiki/Star-free_language" rel="noreferrer">star-free languages</a> are defined with union, concatenation, and complementation.</p>
<p>My question is: <strong>have people studied variants of regular languages and regular language classes where we only allow the disjoint union operator?</strong> For instance, defining a variant of the regular languages by allowing the empty set, the empty word, single letters, and closing under <strong>disjoint</strong> union, concatenation, and Kleene star. (In other words, regular languages where the union operator can only be applied to two languages that are disjoint.) Likewise, defining a variant of star-free languages allowing only disjoint union.</p>
<p>Thinking about the problem (with <a href="https://cstheory.stackexchange.com/users/38111/m-monet">@M.Monet</a> and Charles Paperman), we were surprised to realize that all regular languages, and all star-free languages, appear to be definable with disjoint unions. Specifically:</p>
<ul>
<li><a href="https://en.wikipedia.org/wiki/Kleene%27s_algorithm" rel="noreferrer">Kleene's algorithm</a> applied to a DFA will automatically give a regular expression where the unions are disjoint;</li>
<li>The proof of Schützenberger's theorem turning an aperiodic monoid into a star-free language (see the <a href="https://www.irif.fr/%7Ejep/PDF/MPRI/MPRI.pdf" rel="noreferrer">course notes by J.-É. Pin</a>, Chapter VI, Lemma 3.7, on page labeled 134) seems to use unions that are either disjoint or can be made disjoint.</li>
</ul>
<p>Has this fact been observed anywhere? Has this question of disjoint unions been studied for other classes of regular languages? (Maybe for questions about the size of regular language representations when unions have to be disjoint?)</p>
<p>The only related work I found are notions of unambiguity of regular expressions, for instance <a href="https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous">this question</a>, but they are typically more restrictive; or the notion of <a href="https://www.sciencedirect.com/science/article/pii/S0890540197926882" rel="noreferrer">unambiguity in DTDs</a> but again it seems more restrictive because it is defined via a notion of lookahead.)</p>

CC BY-SA 4.0
2023-02-15T13:46:03.543Z
Out of curiosity, was there a particular motivation to look at this question ?
Denis
CC BY-SA 4.0
2023-02-15T14:08:24.997Z
@Denis: Not really -- we are working on unrelated questions involving disjoint unions, and just got curious.
Antoine Amarilli 'a3nm'
CC BY-SA 4.0
2023-02-15T19:30:20.487Z
This is a really interesting question. I wonder about the density of REs with disjoint union in all REs. I just did a quick heuristic 'Monte-Carlo' simulation: it looks like randomly generated REs have overlapping unions with high probability.
Martin Berger
<reference-request><regular-language><regular-expressions>
Defining regular language classes with disjoint union
Antoine Amarilli 'a3nm'
# Defining regular language classes with disjoint union

(Asked by: username_0 on 2023-02-15)

[Regular languages](https://en.wikipedia.org/wiki/Regular_language) are typically defined using the operations of union, concatenation, and Kleene star. Likewise, there are restricted classes of regular languages defined via similar operations, for instance [star-free languages](https://en.wikipedia.org/wiki/Star-free_language) are defined with union, concatenation, and complementation.

My question is: **have people studied variants of regular languages and regular language classes where we only allow the disjoint union operator?** For instance, defining a variant of the regular languages by allowing the empty set, the empty word, single letters, and closing under **disjoint** union, concatenation, and Kleene star. (In other words, regular languages where the union operator can only be applied to two languages that are disjoint.) Likewise, defining a variant of star-free languages allowing only disjoint union.

Thinking about the problem (with [@M.Monet](https://cstheory.stackexchange.com/users/38111/m-monet) and Charles Paperman), we were surprised to realize that all regular languages, and all star-free languages, appear to be definable with disjoint unions. Specifically:

* [Kleene's algorithm](https://en.wikipedia.org/wiki/Kleene%27s_algorithm) applied to a DFA will automatically give a regular expression where the unions are disjoint;
* The proof of Schützenberger's theorem turning an aperiodic monoid into a star-free language (see the [course notes by J.-É. Pin](https://www.irif.fr/%7Ejep/PDF/MPRI/MPRI.pdf), Chapter VI, Lemma 3.7, on page labeled 134) seems to use unions that are either disjoint or can be made disjoint.

Has this fact been observed anywhere? Has this question of disjoint unions been studied for other classes of regular languages? (Maybe for questions about the size of regular language representations when unions have to be disjoint?)

The only related work I found are notions of unambiguity of regular expressions, for instance [this question](https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous), but they are typically more restrictive; or the notion of [unambiguity in DTDs](https://www.sciencedirect.com/science/article/pii/S0890540197926882) but again it seems more restrictive because it is defined via a notion of lookahead.)

**Tags:** reference-request, regular-language, regular-expressions
> **Comments:**
> **username_1**: Out of curiosity, was there a particular motivation to look at this question ?  
> **username_0**: @Denis: Not really -- we are working on unrelated questions involving disjoint unions, and just got curious.  
> **username_2**: This is a really interesting question. I wonder about the density of REs with disjoint union in all REs. I just did a quick heuristic 'Monte-Carlo' simulation: it looks like randomly generated REs have overlapping unions with high probability.  

---

## 2 answers

### Answer by username_3 on 2023-02-28. Score: 4 | Accepted answer

Interesting, I was recently writing a blog post on a related topic.

Namely, you have probably seen the term *rational languages* used for regular languages. This is because the generating function (g.f.) of a regular language is a rational function.¹
The generating function of the set $A$ is the formal series $$f\_A(X) = \sum\_{n \ge 0} a\_n X^n,$$
where $a\_n = |A\cap\Sigma^n|$ is the number of word of length $n$ in $A$.
A rational function is a function $f$ such that there exists polynomials $P$ and $Q$ such that $f(x) = P(X)/Q(X)$ over the domain of $f$.

The proof goes like this:

1. the g.f. of a finite language is a polynomial,
2. the g.f. of the union of two disjoint languages is the sum of the generating functions
3. under some condition of unambiguity, the g.f. of a concatenation is the product of the g.f.'s and
4. the g.f. of $A^\*$ is $1/(1-f\_A)$ if the Kleene star is "unambiguous".

In points 3 and 4 here, unambiguous means that every word in the resulting language can be obtained in a unique manner using the operation. In that sense, a disjoint union is an unambiguous union.

One then proves that the class of languages obtained from finite languages and applying disjoint union, unambiguous concatenation, and unambiguous Kleene star is equal to regular languages. (I believe this step is basically Kleene's algorithm on a DFA)

See [these lecture notes](https://people.math.carleton.ca/%7Ebsteinbg/classes/automata2009/generatingfunctions.pdf) for full details.

So my answer to your question **Has this fact been observed anywhere?** is **Yes**, and it was also strengthened with an unambiguous version of the other two operations: concatenation and Kleene star.

---

[1]: note, the converse is not true, the set of (even) palindromes is a counterexample.

> **Comments:**
> **username_4**: This is absolutely to the point. I just thought of the old observation that state elimination transforms unambiguous finite automata into unambiguous regular expressions, and wanted to update my answer, then I read yours.  

---

### Answer by username_4 on 2023-02-28. Score: 3

This question has indeed been studied: namely, from the perspective of representing regular languages as unions of so-called *regular components* that is, loop expressions of the form $uv^+w$, and a finite set $F$ of words. Every regular language can be written as the (possibly infinite) disjoint union of regular components and a finite set. See also the references in the following paper:

Y.J. Liu: Regular component decomposition of regular languages, Theoretical Computer Science 299(1–3), 2003, pp. 743-749 <https://doi.org/10.1016/S0304-3975(02)00064-6>

Also somewhat related, the state complexity of disjoint union as a language operation applied to deterministic finite automata was determined here:

Galina Jirásková, Alexander Okhotin: State complexity of unambiguous operations on finite automata, International Conference on Descriptional Complexity of Formal Systems (DCFS) 2018, Lecture Notes in Computer Science Vol. 10952, pp. 188–199 <https://doi.org/10.1007/978-3-319-94631-3_16>

> **Comments:**
> **username_5**: In case someone is as confused as I was: every regular language can be written as a *possibly infinite* disjoint union of regular components and a finite set.  
> **username_0**: Interesting pointers, thanks!  
> **username_4**: @EmilJeřábek thanks, I updated my answer!  

---

