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:
(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].(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.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.
 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.  (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).
 An element s in (S , *) is called zero element of (S , *), if x * s = s * x = s holds for all x Î S.
 An element e of (S , *) is called an identity element of (S , *) provided that s * e = e * s = s holds for all s Î S.
 s is called an idempotent of (S , *), if s * s = s.
 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.
Generally we denote a monoid by a triple (M , * , e)
Examples of Monoids
 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 ·.  The semigroup (R , max) is not a monoid, since there is no identity element.
 The semigroup (S^{S} , ) is a monoid, since the identity mapping is the identity element of (S^{S} , ).
 The semigroup (P(S) , Ç ) for any set S is a monoid, where the set S acts as the identity element of (P(S) , Ç ).
 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.
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_{3}
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^{0} = e, a^{1} = a, a^{2} = 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^{n} 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^{n} for some m, n Î N, thus, we have,
b * c = a^{m} * a^{n} = a^{m+n} = a^{n+m} = a^{n} * a^{m} = c * b.
Examples:
 The semigroup (N , + ) is a cyclic semigroup, since (N , +) is generated by 1, that is, (N , +) = (1).

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:
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+bab
d.a*b=2a +3b
Post a Comment