# rational set

Given an alphabet $\Sigma$, recall that a regular language $R$ is a certain subset of the free monoid $M$ generated by $\Sigma$, which can be obtained by taking singleton subsets of $\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 $\mathcal{S}_{M}$ the set of all singleton subsets of $M$. Consider the closure $\mathcal{R}_{M}$ of $S$ under the operations of union, product, and the formation of a submonoid of $M$. In other words, $\mathcal{R}_{M}$ is the smallest subset of $M$ such that

• $\varnothing\in\mathcal{R}_{M}$,

• $A,B\in\mathcal{R}_{M}$ imply $A\cup B\in\mathcal{R}_{M}$,

• $A,B\in\mathcal{R}_{M}$ imply $AB\in\mathcal{R}_{M}$, where $AB=\{ab\mid a\in A,b\in B\}$,

• $A\in\mathcal{R}_{M}$ implies $A^{*}\in\mathcal{R}_{M}$, where $A^{*}$ is the submonoid generated by $A$.

Definition. A rational set of $M$ is an element of $\mathcal{R}_{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:

• $\varnothing$ and $a$ are regular expressions, for any $a\in M$, representing sets $\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. 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. 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. 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.

## References

Title rational set RationalSet 2013-03-22 19:01:16 2013-03-22 19:01:16 CWoo (3771) CWoo (3771) 8 CWoo (3771) Definition msc 20M35 msc 68Q70 rational language