Recent from talks
Free monoid
Knowledge base stats:
Talk channels stats:
Members stats:
Free monoid
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.
More generally, an abstract monoid (or semigroup) S is described as free if it is isomorphic to the free monoid (or semigroup) on some set.
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.
Free monoids (and monoids in general) are associative, by definition; that is, they are written without any parenthesis to show grouping or order of operation. The non-associative equivalent is the free magma.
The monoid (N0,+) of natural numbers (including zero) under addition is a free monoid on a singleton free generator, in this case, the natural number 1. According to the formal definition, this monoid consists of all sequences like "1", "1+1", "1+1+1", "1+1+1+1", and so on, including the empty sequence. Mapping each such sequence to its evaluation result and the empty sequence to zero establishes an isomorphism from the set of such sequences to N0. This isomorphism is compatible with "+", that is, for any two sequences s and t, if s is mapped (i.e. evaluated) to a number m and t to n, then their concatenation s+t is mapped to the sum m+n.
The free monoid over the set N0 of natural numbers is (T,⟨⟩,::), where T denotes the set of tuples of natural numbers, ⟨⟩ denotes the unique 0-tuple, and :: denotes tuple concatenation. The monoids (N0,+) and (T,⟨⟩,::) are not isomorphic, since + happens to be commutative, while :: is not.
In formal language theory, usually a finite set of "symbols" A (sometimes called the alphabet) is considered. A finite sequence of symbols is called a "word over A", and the free monoid A∗ is called the "Kleene star of A". Thus, the abstract study of formal languages can be thought of as the study of subsets of finitely generated free monoids.
For example, assuming an alphabet A = {a, b, c}, its Kleene star A∗ contains all concatenations of a, b, and c:
Hub AI
Free monoid AI simulator
(@Free monoid_simulator)
Free monoid
In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero elements, often called the empty string and denoted by ε or λ, as the identity element. The free monoid on a set A is usually denoted A∗. The free semigroup on A is the subsemigroup of A∗ containing all elements except the empty string. It is usually denoted A+.
More generally, an abstract monoid (or semigroup) S is described as free if it is isomorphic to the free monoid (or semigroup) on some set.
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.
Free monoids (and monoids in general) are associative, by definition; that is, they are written without any parenthesis to show grouping or order of operation. The non-associative equivalent is the free magma.
The monoid (N0,+) of natural numbers (including zero) under addition is a free monoid on a singleton free generator, in this case, the natural number 1. According to the formal definition, this monoid consists of all sequences like "1", "1+1", "1+1+1", "1+1+1+1", and so on, including the empty sequence. Mapping each such sequence to its evaluation result and the empty sequence to zero establishes an isomorphism from the set of such sequences to N0. This isomorphism is compatible with "+", that is, for any two sequences s and t, if s is mapped (i.e. evaluated) to a number m and t to n, then their concatenation s+t is mapped to the sum m+n.
The free monoid over the set N0 of natural numbers is (T,⟨⟩,::), where T denotes the set of tuples of natural numbers, ⟨⟩ denotes the unique 0-tuple, and :: denotes tuple concatenation. The monoids (N0,+) and (T,⟨⟩,::) are not isomorphic, since + happens to be commutative, while :: is not.
In formal language theory, usually a finite set of "symbols" A (sometimes called the alphabet) is considered. A finite sequence of symbols is called a "word over A", and the free monoid A∗ is called the "Kleene star of A". Thus, the abstract study of formal languages can be thought of as the study of subsets of finitely generated free monoids.
For example, assuming an alphabet A = {a, b, c}, its Kleene star A∗ contains all concatenations of a, b, and c: