5
$\begingroup$

Let $M$ be a monoid (e.g. $M = \Sigma^*$) and $L \subseteq M$.

Then $\mathsf{RAT}(M)$ is the set of rational sets of $M$ and the elements of $\mathsf{RAT}(M)$ are inductively defined as follows:

  • $|L| < \infty \implies L \in \mathsf{RAT}(M)$
  • $L_1, L_2 \in \mathsf{RAT}(M) \implies L_1 \cup L_2 \in \mathsf{RAT}(M)$
  • $L_1, L_2 \in \mathsf{RAT}(M) \implies L_1 \cdot L_2 \in \mathsf{RAT}(M)$
  • $L \in \mathsf{RAT}(M) \implies L^\ast = \bigcup_{i \geq 0} L^i \in \mathsf{RAT}(M)$ with $L^0=\{1_m\}$ and $L^{i+1} = L^iL$

And in my understanding, a rational expression is then an expression using only the operations in this definition, i.e. $$L_1 \cup L_2 \cup L_3L_4 \cup L_3^*$$.

On the other hand we have the definition of regular languages where $\mathsf{REG(M)}$ is the set of regular sets inductivly defined as follows:

  • $\emptyset$ is a regular expression
  • $\epsilon $ is a regular expression
  • $a \in \Sigma$ is a regular expression
  • if $\alpha$ and $\beta$ are regular expressions, then $\alpha\mid\beta$ is a regular expression
  • $\alpha^*$ and $\alpha\beta$ are regular expressions

Futhermore we know that regular languages are closed under complement unlike rational languages.

Question: It is often stated that regular expressions are the same as rational expressions. But hence this defintion of a rational expression doesn't allow for example "the decision"-operator, ($a \mid b$), it seems that regular expressions cover more than rational ones. What am I missing out? Are they really the same and if not, where are they distinct?

$\endgroup$
8
  • 3
    $\begingroup$ What's the difference between $\mid$ and $\cup$? $\endgroup$
    – rici
    Commented Mar 18, 2021 at 14:38
  • $\begingroup$ Your definition of regular expressions is missing concatenation. But anyway, rici is right. $\endgroup$ Commented Mar 18, 2021 at 14:51
  • $\begingroup$ Hmm, ok thank you :) But if they are equal, why do we need two names for the same thing? $\endgroup$
    – Algebruh
    Commented Mar 18, 2021 at 14:54
  • 3
    $\begingroup$ The set of regular languages over an alphabet $\Sigma$ is the same as the set of rational sets of the free monoid $\Sigma^*$. However, the concept of rational sets is defined for any monoid, it doesn't need to be free, for example. $\endgroup$
    – plop
    Commented Mar 18, 2021 at 15:31
  • 1
    $\begingroup$ Well, those are just names and not content. I suppose you could find authors using the name regular sets for any monoid, or using the two words interchangeably. $\endgroup$
    – plop
    Commented Mar 18, 2021 at 16:20

2 Answers 2

4
$\begingroup$

A late but detailed answer.

First of all, the term regular is one of the most overloaded term in mathematics (see the impressive list Regular/Mathematics on Wikipedia). In particular, if you ask for the definition of a regular language to a computer scientist, some people will say that it is a language recognised by a finite automaton and some other people will say that is a language defined by a regular expression.

This is fine as long as you talk about languages since Kleene theorem tells you that the two definitions are equivalent. This is another story when you deal with abstract monoids (not necessarily free!). As you recalled in your answer, the set of rational subsets of a monoid $M$ is the smallest set of subsets of $M$ containing the singletons and closed under finite union, product and star (where $L^*$ is the submonoid of $M$ generated by $L$). But there is also another definition, which can be seen as an abstract version of recognition by a finite device:

Definition. A subset $L$ of $M$ is recognizable if there exist a finite monoid $F$, a surjective monoid morphism $f\colon M \rightarrow F$ and a subset $P$ of $F$ such that $L = f^{-1}(P)$.

Unfortunately, Kleene's theorem does not extend to arbitrary monoids, that is, rational and recognizable are not in general equivalent notions. For instance, I let you verify that $\{0\}$ is a rational subset of the additive monoid $\Bbb{Z}$ but is not recognisable. Thus it would be highly confusing to use the term regular in the context of monoids and I strongly recommend against it.

Just for the record, let me mention a weaker property, that holds for finitely generated monoids.

Theorem [McKnight 1964] Let $M$ be a monoid. The following conditions are equivalent:

  1. $M$ is finitely generated,
  2. every recognizable subset of $M$ is rational,
  3. the set $M$ is a rational subset of $M$.
$\endgroup$
1
$\begingroup$

The usage that I've seen, have been told of, and that I recommend is "rational" if the underlying monoid is non-free, "regular" for free monoids.

Examples showing this, which I've pulled out from a cursory search are:

"Rational Transductions"; i.e. rational subsets of a product monoid $X^* × Y^*$ in section 4 of Transductions and Context-Free Languages (PDF), actually they're using "rational transduction" if it's a function, and "rational relation" in the more generic case

Render & Kambites, "Rational Subsets Of Polycyclic Monoids And Valence Automata" (ArXiv 0710.3711v1)

Silva, "On the rational subsets of the monogenic free inverse monoid", Journal of Algebra 618, 214-240

Eilenberg & Schütezenberger, "Rational Sets in Commutative Monoids", Journal of Algbera 13(2), 173-191

$\endgroup$

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.