You are here
Homerational set
Primary tabs
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. 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.
References
 1 S. Eilenberg, Automata, Languages, and Machines, Vol. A, Academic Press (1974).
Mathematics Subject Classification
20M35 no label found68Q70 no label found Forums
 Planetary Bugs
 HS/Secondary
 University/Tertiary
 Graduate/Advanced
 Industry/Practice
 Research Topics
 LaTeX help
 Math Comptetitions
 Math History
 Math Humor
 PlanetMath Comments
 PlanetMath System Updates and News
 PlanetMath help
 PlanetMath.ORG
 Strategic Communications Development
 The Math Pub
 Testing messages (ignore)
 Other useful stuff
 Corrections