1. Introduction to monoids

Mikołaj Bojańczyk

zajęcia / courses

A monoid is a set with an empty element, and an associative multiplication operation. We present two formal definitions of this concept, namely the classical one in Definition 1, and a slightly nonstandard one in Definition 2.

Definition 1. A monoid consists of a universe $M$ together with an identity element $1 \in M$ and a multiplication operation, denoted multiplicatively, which is associative in the sense that

$(m \cdot n) \cdot k = m \cdot (n \cdot k)$

holds for every $m,n,k \in M$ . $\Box$

The definition says that the order of evaluation in a monoid is not important, i.e. that different ways of parenthesising a sequence of elements in the monoid will yield the same result as far as monoid multiplication is concerned. This is made explicit in the following fact, which is implicitly presented to students already in primary school (at least this was the case for me).

Fact 1. Let $M$ be a monoid, and let $m_1,\ldots,m_k$ be a sequence of elements in $M$ . For any possible way of parenthesising the sequence and multiplying it in the monoid, the result is the same.

Proof. A parenthesisation can be viewed as a binary tree, where the leaves are labelled by $m_1,\ldots,m_k$ when read from left to right. The associativity equation in Definition 1 says that doing a rotation does not affect the value of a tree. Every two trees that have the same sequence of leaves can be transformed into each other using a finite sequence of rotations. $\Box$

In light of the above proof, the definition of associativity in Definition 1 might seem a little bit of a hack. An alternative definition is presented below. The key is that the multiplication operation is no longer binary, but takes in an arbitrary word. This allows a new statement of the associativity condition, in the form of a commuting diagram. The new statement, easily seen to be equivalent with the classical definition in Definition 1, will be a basis for further generalisations later in the lecture. Also because of these later generalisations, we write some of the subsequence definitions, like homomorphisms, in terms of commuting diagrams.

Definition 2. A monoid consists of a universe $M$ together with a multiplication operation

$\multnoarg : M^* \to M$

which maps each one letter word $m$ to $m$ , and which is associative in the sense that the following diagram commutes

$\xymatrix{(M^*)^* \ar[r]^{\flattnoarg} \ar[d]_{\multnoarg^*} & M^* \ar[d]^{\multnoarg} \\ M^* \ar[r]_{\multnoarg} & M}$

where $\flattnoarg$ flattens a word of words into a word in the obvious way, while $\multnoarg^*$ applies the multiplication operation to every word in a word of words.

Fact. The two definitions are the same.

Proof. Using Fact 1. $\Box$

Example 1. If $\Sigma$ is a set, then $\Sigma^*$ is a monoid, where the identity is the empty words, and concatenation is the monoid operation. $\Box$

Monoid homomorphisms

A monoid homomorphism if a function between monoids that preserves the structure of monoids, i.e. a monoid homomorphism between monoids $M$ and $N$ is a function

$h : M \to N$

which preserves the identity element and which is consistent with the multiplication operation in the sense that

$h(m \cdot n) = h(m) \cdot h(n)$

An alternative definition of a homomorphism would be that the following diagram commutes

$\xymatrix{M^* \ar[r]^{h^*} \ar[d]_{\mult M} & N^* \ar[d]^{\mult N} \\ M \ar[r]_h & N}$

with the two downward arrows representing the multiplication operations in the respective monoids.

Using monoid homomorphisms, we can express the following universal property of the monoid $\Sigma^*$ . It is generated by $\Sigma$ , and it is the biggest monoid generated by $\Sigma$ in the following sense. For every monoid $N$ that is generated by $\Sigma$ , there exists a surjective monoid homomorphism

$h : \Sigma^* \to M$

which is the identity on the $\Sigma$ generators. This is property goes under the name “ $\Sigma^*$ is the free monoid with generators $\Sigma$ “.

Monoid homomorphisms are closely related with functions that are compositional in the sense defined below. Let $M$ be a monoid, and let $X$ be a set. A function

$h : M \to X$

is called compositional if for every $m, n \in M$ , the value $h(m \cdot n)$ is uniquely determined by the values $h(m)$ and $h(n)$ . Again, compositionality can be stated in terms of terms of a commuting diagram: $h$ is compositional if there is some function $\mult X$ such that the following diagram commutes:

$\xymatrix{M^* \ar[r]^{h^*} \ar[d]_{\mult M} & X^* \ar[d]^{\mult X} \\ M \ar[r]_h & X}$

Lemma. Let $M$ be a monoid, and let $h : M \to X$ be a sujrective compositional function. Then there exists (a unique) monoid structure on $X$ which makes $h$ into a monoid homomorphism.

Proof. Saying that $h(m \cdot n)$ is uniquely determined by $h(m)$ and $h(n)$ , as in the definition of compositionally, means that there is a function

$f : X \times X \to X$

such that every $m,n \in M$ satisfy

$h(m \cdot n) = f(h(m),h(n)).$

One uses $f$ to be the product operation in $X$ , and takes the identity to be the image under $h$ of the identity. $\Box$

Recognising languages

In this lecture, we will be interested in monoid as an alternative to finite automata, i.e. we will use monoids to recognise languages.

Definition. A language $L \subseteq A^*$ is said to be recognised by a monoid homomorphism

$h : A^* \to M$

if membership in $w \in L$ is determined uniquely by $h(w)$ . In other words, there exists a subset $F \subseteq M$ such that

$w \in L \qquad\text{iff} \qquad h(w) \in F$

holds for every word $w \in A^*$ . $\Box$

The following theorem shows that, as far as recognising languages is concerned, finite monoids and finite automata are equivalent.

Theorem 1. The following conditions are equivalent for every language $L \subseteq A^*$ :
• $L$ is recognised by a finite automaton;
• $L$ is recognised by a monoid homomorphism into a finite monoid.

Proof. From a monoid one creates a deterministic automaton, whose states are elements of the monoid, and where the transition relation is obtained from the monoid operation in the obvious way. This proves the bottom-up implication. For the top-down implication, let us transform a nondeterministic automaton into a monoid. Let $\mathcal A$ be a nondeterministic automaton with input alphabet $A$ and states $Q$ . Define the function

$\delta : A^* \to P(Q \times Q)$

which sends a word $w$ to the set of pairs $(p,q)$ such that there exists a run of the automaton which begins in $p$ , reads the word $w$ , and ends in $q$ . One can show that $\delta$ is compositional, and therefore there is a monoid structure on its image which makes it into a monoid homomorphism. The appropriate multiplication operation is simply composition of relations, while the identity is the identity relation. $\Box$

Note how the transformation from a nondeterministic finite automaton to a monoid incurs an exponential blowup. Note also that the transformation from nondeterministic finite automaton to a deterministic finite automaton is exponential, but going directly from a nondeterministic finite automaton to monoids is not doubly exponential.

The syntactic monoid

Deterministic finite automaton have minimisation, i.e. there is always a minimal deterministic automaton that can be obtained from any other automaton by quotienting. The same holds for monoids, as proved in the following theorem.

Theorem 2. For every language $L \subseteq A^*$ there exists a monoid homomorphism

$h : A^* \to M,$

called the syntactic homomorphism of $L$ , which recognises it and is minimal in the sense that for every surjective monoid homomorphism

$g : A^* \to N$

which also recognises $L$ , there exists a unique monoid homomorphism which makes the following diagram commute

$\xymatrix{ A^* \ar[r]^h \ar[dr] _g& M \\ & N\ar[u]_f }$

Proof. Define the syntactic equivalence of $L$ to be the equivalence relation on $A^*$ which identifies two words $w,w' \in A^*$ if

$wuv \in L \qquad\text{iff} \qquad wu'v \in L$

holds for every $u,v \in A^*$ . One can show that the function, call it $h$ , that maps a word to its equivalence class is compositional, and therefore by Lemma 1, the set of equivalence classes is equipped with a monoid structure that makes $h$ into a monoid homomorphism. It is not difficult to check that $h$ is minimal as required in the theorem. $\Box$

Exercise. Prove that surjectivity is important in the above theorem.

COMMENTS

Mikołaj

July 17, 2023

By the way, there are better lecture notes now: https://www.mimuw.edu.pl/~bojan/paper/book-on-languages-recognised-by-finite-semigroups

Soumodev

July 15, 2023

Hi! Thanks for your concise explanation and nice intuitions. There is a small typo that I would like to point out. It's in the definition of syntactic equivalence. Shouldn't it be \[uwv \in L \qquad\text{iff} \qquad uw'v \in L\]? Thanks again :-)

Zubair

May 21, 2023

Best explanation.. Thank you

Ahmed

September 29, 2018

Thank you for writing this concise lesson. However, I think adding examples and expanding the phrases/words (in an obvious way, monoid [without specifying the operation]) would improve the clarity of the lesson

Ohad

January 16, 2018

Thanks for this all!

zajęcia / courses

1. Introduction to monoids

Leave a Reply