rational set

Given an alphabet $\mathrm{\Sigma }$, recall that a regular language $R$ is a certain subset of the free monoid $M$ generated by $\mathrm{\Sigma }$, which can be obtained by taking singleton subsets of $\mathrm{\Sigma }$, and perform, in a finite number of steps, any of the three basic operations: taking union, string concatenation, and the Kleene star.

The construction of a set like $R$ is still possible without $M$ being finitely generated free.

Let $M$ be a monoid, and ${𝒮}_M$ the set of all singleton subsets of $M$. Consider the closure ${ℛ}_M$ of $S$ under the operations of union, product, and the formation of a submonoid of $M$. In other words, ${ℛ}_M$ is the smallest subset of $M$ such that

• $\mathrm{\varnothing }\in {ℛ}_M$,

• $A,B\in {ℛ}_M$ imply $A\cup B\in {ℛ}_M$,

• $A,B\in {ℛ}_M$ imply $AB\in {ℛ}_M$, where $AB=\{ab\mid a\in A,b\in B\}$,

• $A\in {ℛ}_M$ implies $A^{*}\in {ℛ}_M$, where $A^{*}$ is the submonoid generated by $A$.

Definition. A rational set of $M$ is an element of ${ℛ}_M$.

If $M$ is a finite generated free monoid, then a rational set of $M$ is also called a rational language, more commonly known as a regular language.

Like regular languages, rational sets can also be represented by regular expressions. A regular expression over a monoid $M$ and the set it represents are defined inductively as follows:

• $\mathrm{\varnothing }$ and $a$ are regular expressions, for any $a\in M$, representing sets $\mathrm{\varnothing }$ and $\{a\}$ respectively.

• if $a,b$ are regular expressions, so are $a\cup b$, $ab$, and $a^{*}$. Furthermore, if $a,b$ represent sets $A,B$, then $a\cup b$, $ab$, and $a^{*}$ represent sets $A\cup B$, $AB$, and $A^{*}$ respectively.

Parentheses are used, as usual, to avoid ambiguity.

From the definition above, it is easy to see that a set $A\subseteq M$ is rational iff it can be represented by a regular expression over $M$.

Below are some basic properties of rational sets:

1. Any rational set $M$ is a subset of a finitely generated submonoid of $M$. As a result, every rational set over $M$ is finite iff $M$ is locally finite (meaning every finitely generated submonoid of $M$ is actually finite).

2. Rationality is preserved under homomorphism: if $A$ is rational over $M$ and $f:M\to N$ is a homomorphism, then $f(A)$ is rational over $N$.

3. Conversely, if $B\in f(M)$ is rational over $N$, then there is a rational set $A$ over $M$ such that $f(A)=B$. Thus if $f$ is onto, every rational set over $N$ is mapped by a rational set over $M$. If $f$ fails to be onto, the statement becomes false. In fact, inverse homomorphisms generally do not preserve rationality.