Given an alphabet , recall that a regular language is a certain subset of the free monoid generated by , which can be obtained by taking singleton subsets of , 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 is still possible without being finitely generated free.
Let be a monoid, and the set of all singleton subsets of . Consider the closure of under the operations of union, product, and the formation of a submonoid of . In other words, is the smallest subset of such that
imply , where ,
implies , where is the submonoid generated by .
Definition. A rational set of is an element of .
If is a finite generated free monoid, then a rational set of 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 and the set it represents are defined inductively as follows:
and are regular expressions, for any , representing sets and respectively.
if are regular expressions, so are , , and . Furthermore, if represent sets , then , , and represent sets , , and respectively.
Parentheses are used, as usual, to avoid ambiguity.
From the definition above, it is easy to see that a set is rational iff it can be represented by a regular expression over .
Below are some basic properties of rational sets:
Any rational set is a subset of a finitely generated submonoid of . As a result, every rational set over is finite iff is locally finite (meaning every finitely generated submonoid of is actually finite).
Rationality is preserved under homomorphism: if is rational over and is a homomorphism, then is rational over .
|Date of creation||2013-03-22 19:01:16|
|Last modified on||2013-03-22 19:01:16|
|Last modified by||CWoo (3771)|