rational set


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

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

Let M be a monoid, and 𝒮M the set of all singleton subsets of M. Consider the closureMathworldPlanetmath M of S under the operations of union, productMathworldPlanetmathPlanetmath, and the formation of a submonoid of M. In other words, M is the smallest subset of M such that

  • M,

  • A,BM imply ABM,

  • A,BM imply ABM, where AB={abaA,bB},

  • AM implies A*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 expressionsMathworldPlanetmath. A regular expression over a monoid M and the set it represents are defined inductively as follows:

  • and a are regular expressions, for any aM, representing sets and {a} respectively.

  • if a,b are regular expressions, so are ab, ab, and a*. Furthermore, if a,b represent sets A,B, then ab, ab, and a* represent sets AB, AB, and A* respectively.

Parentheses are used, as usual, to avoid ambiguity.

From the definition above, it is easy to see that a set AM 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 finitePlanetmathPlanetmathPlanetmath (meaning every finitely generated submonoid of M is actually finite).

  2. 2.

    Rationality is preserved under homomorphismPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath: if A is rational over M and f:MN is a homomorphism, then f(A) is rational over N.

  3. 3.

    Conversely, if Bf(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, inverseMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath homomorphisms generally do not preserve rationality.

References

Title rational set
Canonical name RationalSet
Date of creation 2013-03-22 19:01:16
Last modified on 2013-03-22 19:01:16
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Definition
Classification msc 20M35
Classification msc 68Q70
Defines rational language