Tuesday, August 12, 2008

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 SS be the set of all mappings from S to S and let denote the composition of mappings.
    Then (SS , ) is a semigroup.
Proof:

Let S be any nonempty set.
Let SS = {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 Î SS.
Hence, (SS,) is a semigroup.
  1. 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.
  2. (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 (SS , ) is a monoid, since the identity mapping is the identity element of (SS , ).
  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 Mn denote the set of all n x n matrices over the real numbers. Then (Mn , +) and (Mn , ·) 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 Zm denote the set of all distinct equivalence classes defined by the equivalence relation "º (mod m)" [For, example Z3
consists of the distinct equivalence classes [0], [1] and [2]]

Define the operations Å and ¤ on the set Zm by [a] Å [b] = [ (a + b) (mod m)] and [a] ¤ [b] = [(a · b) (mod m)].
Then for all, [a], [b] and [c] in Zm, 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] Î Zm.

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


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 (Mn , ·) 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
a0 = e, a1 = a, a2 = 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 an 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 = am and c = an for some m, n Î N, thus, we have,
b * c = am * an = am+n = an+m = an * am = 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.

1 comment:

arnold said...

PLEASE answer this

Determine which of the following are semigroups under the set of real numbers where, the operation is defined as

a. a*b = a+b
b. a*b = ab
c.a*b = a+b-ab
d.a*b=2a +3b