Semigroups and Monoids

Semigroups play a fundamental role in the Algebraic Automata Theory and the Theory of Formal Languages. In this chapter
we discuss introductory results on semigroups, monoids and grammars and some popular examples..

A nonempty set S together with a binary operation *, (S, *), is called a semigroup, if for all a, b, cÎ S,
a * (b*c) = (a * b) * c.

Examples of Semigroups:

1. (N , +) , (N , ·), (Z , +), (Z , ·), (Q , +), (Q , ·), (R , +), (R , ·), (C , +) and (C , ·) are all semigroups, where N, Z, Q, R
   and C respectively denote the set of natural numbers, the set of integers, the set of rational numbers, the set of real
   numbers and the set of complex numbers and + and · denote usual addition and usual multiplication of number. [It is
   clear that + and · are associative on the above number system].
2. (R, max), where R the set of real number and x max y = max (x, y) is a semigroup.
   For, (x max y) max z = (max (x , y)) max z
   = max (max (x , y), z)
   = max (x , y , z)
   = max (x, max (y, z))
   = x max (max (y , z))
   = x max (y max z) , for all x, y, z Î R.
   Thus, (R, max) is a semigroup.
3. Let S be any nonempty set. Let S^S be the set of all mappings from S to S and let denote the composition of mappings.
   Then (S^S , ) is a semigroup.

Proof:

Let S be any nonempty set.
Let S^S = {f / f: S ® S be any mapping}.
Then, the composition of mapping f g is defined by
(f g)(x) = f(g(x)), for all x Î S, is assosiative.
For, (f g) h)(x) = (f g) (h(x)) = f(g(h(x))), for all x Î S and
on the other hand, (f(gh)) (x) = f((gh)(x)) = f(g(h(x))), for all x Î S.
Thus, (fg) h = (fg) h, for all f, g, h Î S^S.
Hence, (S^S,) is a semigroup.

4. Let S be any set. Then (P(S) , Ç ) is a semigroup, where P(S) denote the power set of S. Let A, B and C be any three
   subsets of S. Then, (A Ç B) Ç C = A Ç (B Ç C).
   For, x Î (A Ç B) Ç C Û x Î A Ç B and x Î C
   Û x Î A and x Î B and x Î C
   Û x Î A and x Î B Ç C
   Û x Î A Ç (B Ç C).
   Hence, (P(S) , Ç ) is a semigroup.
5. (Z , -) is not a semigroup since the operation "-" is not associative.
   For, (5 - 3) - 2 = 2 - 2 = 0, where as 5 - (3 - 2) = 5 - 1 = 4, definitely, (5 - 3) - 2 ¹5 - (3 - 2).

Let (S , *) be a semigroup.

1. An element s in (S , *) is called zero element of (S , *), if x * s = s * x = s holds for all x Î S.
2. An element e of (S , *) is called an identity element of (S , *) provided that s * e = e * s = s holds for all s Î S.
3. s is called an idempotent of (S , *), if s * s = s.
4. An element s in (S ,* ) is said to be an invertible if there exists an element r in (S , *) such that s * r = e = r * s.

A semigroup (S , *) is called a monoid if there is an identity element ‘e’ in (S , *).

Generally we denote a monoid by a triple (M , * , e)



Examples of Monoids

1. In the Example1 of the semigroups given above, except the semigroup (N , +), all the other semigroups are monoids. Since
   all the number system except N, have identity elements 0 and 1 respectively for the operations + and ·.
2. The semigroup (R , max) is not a monoid, since there is no identity element.
3. The semigroup (S^S , ) is a monoid, since the identity mapping is the identity element of (S^S , ).
4. The semigroup (P(S) , Ç ) for any set S is a monoid, where the set S acts as the identity element of (P(S) , Ç ).
5. Let M_n denote the set of all n x n matrices over the real numbers. Then (M_n , +) and (M_n , ·) are monoids, where ‘+’ is the
   matrix addition and ‘·’ is the matrix multiplication. Zero matrix acts as additive identity and unit matrix acts as multiplicative
   identity.

The following two examples of monoid deserve a special attention.

Example 6: Monoid of "Integer congruence Modulo"

Let Z be the set of all integers. Define a relation "º (mod m)" on the set of integers Z by a º b (mod m) if and only if
"m divides (a – b)", that is, "m½(a – b)".
Then, "º (mod m)" is reflexive.
For, any fixed m, m½(a – a), for all aÎ Z.
Therefore, a º a (mod m).
Also, "º (mod m)" is symmetry.
For, if a º b (mod m), then m½(a – b).
Therefore, m½-(a - b), that is, m½(b – a).
Thus, b º a (mod m).
Further, if a º b (mod m) and b º c (mod m), then m½(a – b) and m½(b – c) .
Therefore, m½((a - b) + ( b - c)) , that is, m½(a – c).
Thus, a º c (mod m).
Hence, "º (mod m)" is transitive.
Hence, "º (mod m)" is an equivalence relation.

Let [a] = {x Î Z / x º a (mod m) }, denote the equivalence class of a Î Z defined by the equivalence relation "º (mod m)".

Let Z_m denote the set of all distinct equivalence classes defined by the equivalence relation "º (mod m)" [For, example Z₃
consists of the distinct equivalence classes [0], [1] and [2]]

Define the operations Å and ¤ on the set Z_m by [a] Å [b] = [ (a + b) (mod m)] and [a] ¤ [b] = [(a · b) (mod m)].
Then for all, [a], [b] and [c] in Z_m, we have,
([a] Å [b]) Å [c] = [(a + b)(mod m)] Å [c] (by definition of Å )
= [((a + b)(mod m) + c)(mod m)]
= [(a + b + c)(mod m)] (by definition of 'mod m')
= [(a + (b + c)(mod m)] (since + is associate in the integers)
= [(a + ((b + c)(mod m))(mod m)]
= [a] + [(b + c)(mod m)]
= [a] + ([b] + [c])

Similarly, we can show that ([a] ¤ [b]) ¤ [c] = [a] ¤ ([b] ¤ [c]), for all, [a], [b], [c] Î Z_m.

Also, note that the equivalence class [0] act as an identity element in (Z_m , Å ) and the equivalence class [1] act as an identity
element in (Z_m , ¤ ).


Example 7: Monoids of strings over an alphabet

Let å be a nonempty set, may be finite or countable, called alphabet. The elements of å are called symbols or letters or
characters. A string or word over an alphabet å is an ordered set of symbols from the alphabet. A string consisting of m
symbols (m > 0) is called a string of length m. A string of length zero, that is, string consisting of no symbols is called
empty string and it is denoted by L . Let å * denote the set of all strings over å and let å ⁺ denote the set of all nonempty
strings over å .

Let a , b Î å * . Define a binary operation ‘’called concatenation operation on strings by ab = a b

[For example, a = aabbab and b = abbbaa over å = {a, b}, then ab = a b = aabbababbbaa].

Then (å * , ) is a monoid and (å ⁺ , ) is a semigroup.
For a(bg ) = a(b g ) = a (b g ) = (a b )g = (ab )g = (ab )g , for all a , b , g Î å *.

Note that the empty string L acts as an identity element since La = aL = a , for all a Î å *.
Hence (å ⁺, ) is a semigroup and (å ^*, ) is a monoid.

The semigroup (å ⁺,) is also called free semigroup and (å ^* , ) is also called free monoid.

The free semigroup and free monoid play an important role in the "Theory of Formal Languages and Automata".

A semigroup (monoid) (S , *) is called commutative if a * b = b * a, for all a, b Î S.

If in a monoid (M , * , e) every element is invertible, then the monoid is called group.

For example, (Z , +) is commutative monoid and it is a group also. The monoid (M_n , ·) is not commutative, and it is not a
group.

In a monoid (M , *), the powers of any particular element say a Î M are defined as
a⁰ = e, a¹ = a, a² = a * a, … , a ^{j +1} = a ^j * a, for j Î N.

A monoid (M , * , e) is said to be cyclic if there exists an element a Î M such that every element of M can be expressed
as some power of a, that is, as aⁿ for some n Î N. In such a case, the cyclic monoid is said to be generated by the
element ‘a’ and the element ‘a’ is called generator of the cyclic monoid.


Remark:

A cyclic monoid is always commutative, since, for any b, c Î M, b = a^m and c = aⁿ for some m, n Î N, thus, we have,
b * c = a^m * aⁿ = a^m+n = a^n+m = aⁿ * a^m = c * b.

Examples:

1. The semigroup (N , + ) is a cyclic semigroup, since (N , +) is generated by 1, that is, (N , +) = (1).
2. 
   The semigroup (N, ·) is a cyclic monoid, since any natural number can be expressed as product of powers of primes,
   that is (N , ·) is a cyclic monoid generated by the set of all primes and 1.