free monoid
free monoid A particular kind of monoid, usually involving strings. Note first that concatenation is an associative operation and also that, if Λ is the empty string, then Λw = w = wΛ
for all strings w, i.e. Λ is an identity element. Hence, for any alphabet A (see formal language), the set of all A-words forms a monoid under concatenation. Furthermore this monoid has the algebraic property of “freeness”, which here means that, given any other monoid M and a function f from A to M, there is precisely one way of extending f to a monoid homomorphism from A* to M. There are other free monoids, but they are all isomorphic to monoids of strings under concatenation. Hence the latter are representative of the free monoids and the phrase is often taken to refer to them specifically. See also initial algebra.
for all strings w, i.e. Λ is an identity element. Hence, for any alphabet A (see formal language), the set of all A-words forms a monoid under concatenation. Furthermore this monoid has the algebraic property of “freeness”, which here means that, given any other monoid M and a function f from A to M, there is precisely one way of extending f to a monoid homomorphism from A* to M. There are other free monoids, but they are all isomorphic to monoids of strings under concatenation. Hence the latter are representative of the free monoids and the phrase is often taken to refer to them specifically. See also initial algebra.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
free monoid