9
$\begingroup$

Regular languages 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 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 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 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, 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, but they are typically more restrictive; or the notion of unambiguity in DTDs but again it seems more restrictive because it is defined via a notion of lookahead.)

$\endgroup$
3
  • $\begingroup$ Out of curiosity, was there a particular motivation to look at this question ? $\endgroup$
    – Denis
    Commented Feb 15, 2023 at 13:46
  • $\begingroup$ @Denis: Not really -- we are working on unrelated questions involving disjoint unions, and just got curious. $\endgroup$
    – a3nm
    Commented Feb 15, 2023 at 14:08
  • $\begingroup$ 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. $\endgroup$ Commented Feb 15, 2023 at 19:30

2 Answers 2

4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Feb 28, 2023 at 22:12
3
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Feb 28, 2023 at 11:10
  • $\begingroup$ Interesting pointers, thanks! $\endgroup$
    – a3nm
    Commented Feb 28, 2023 at 12:26
  • $\begingroup$ @EmilJeřábek thanks, I updated my answer! $\endgroup$ Commented Feb 28, 2023 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.