| • Science | • People | • Locations | • Timeline |
For example, if A = {a, b, c} elements of A* are of the form
The free semigroup on A is the sub semigroup of A* containing all elements except the empty string. It is usually denoted A+.
More generally, a moniod (or semigroup) S is described as free if it is isomorphic to the free monoid (or semigroup) on some set. A set of elements which maps onto the set of single-letter words under such an isomorphism is called a set of free generators for S. Each free semigroup (or monoid) S has exactly one set of free generators, the cardinality of which is called the rank of S.
For example, the monoid of natural numbers under addition is a free monoid on a single generator (i.e. rank 1). The unique free generator is the number 1.
Two free monoids or semigroups are isomorphic if and only if they have the same rank. In fact, every set of generators for a free semigroup or monoid S contains the free generators. It follows that a free semigroup or monoid is finitely generated if and only if it has finite rank.
As the name implies, free monoids and semigroups are those objects which satisfy the usual universal property defining free objects, in the respective categories of monoids and semigroups. It follows that every monoid (or semigroup) arises as a homomorphic image of a free monoid (or semigroup). The study of semigroups as images of free semigroups is called combinatorial semigroup theory .
If A is a set, the word length function on A* is the unique monoid homomorphism from A* to N that maps each element of A to 1.
If Σ is a finite alphabet (a set of symbols), then Σ* consists of all words over Σ in the sense of formal languageIn mathematics, logic and computer science, a formal language is a set of finite-length words (i. character strings) drawn from some finite alphabet, and the scientific theory that deals with these entities is known as formal language theory''. Note that theory. Thus, the abstract study of formal languages can be thought of as the study of subsets of finitely generated free monoids. There are deep connections between the theory of semigroups and that of automataA field of computer science which studies Finite state machines, by means of mathematical representations of them (automata, Turing machines). Below you will find a brief reference on how general automata are constructed and how they "work". Turing machin. For example, the regular languageA regular language is a formal language (i. a possibly infinite set of finite sequences of symbols from a finite alphabet) that satisfies the following equivalent properties: it can be accepted by a deterministic finite state machine it can be accepted bys over Σ are the homomorphic pre-images in Σ* of subsets of finite monoids.