. 6
( 13)


of G 0
Column ’ |Stab x|


Example 6.2. Three black and six white beads are strung onto a circular wire.
This necklace can be rotated in its plane, and turned over. How many differ-
ent types of necklaces can be made assuming that beads of the same color are

Solution. Position the three black and six white beads at the vertices of a
regular 9-gon. If the 9-gon is ¬xed, there are 9 · 8 · 7/3! = 84 different ways of
doing this. Two such arrangements are equivalent if there is an element of the
symmetry group of the regular 9-gon, D9 , which takes one arrangement into the
other. The group D9 permutes the different arrangements, and the number of
nonequivalent arrangements is the number, N , of orbits under D9 . We can now
use the Burnside theorem to ¬nd N .
Table 6.2 lists all the different types of elements of D9 and the number of
¬xed points for each type. For example, consider the re¬‚ection g ∈ D9 about the
line joining vertex 2 to the center of the circle, which is illustrated in Figure 6.1.
Then the arrangements that are ¬xed under g occur when the black beads are
at vertices 1 2 3, 9 2 4, 8 2 5, or 7 2 6. Hence |Fix g| = 4. There are nine
re¬‚ections about a line, one through each vertex. Therefore, the total number of
¬xed points contributed by these types of elements is 9 · 4 = 36. A rotation of
order 3 in D9 will ¬x an arrangement if the black beads are at vertices 1 4 7, 2 5
8, or 3 6 9; hence there are three arrangements that are ¬xed. If an arrangement
is ¬xed under a rotation of order 9, all the beads must be the same color; hence
|Fix g| = 0 if g has order 9. Table 6.2 shows that the sum of all the numbers of
1 126
¬xed points is 126. By Theorem 6.1, N = |Fix g| = = 7, and
|D9 | g∈D9 18
there are seven different types of necklaces.

In this example, it is easy to determine all the seven types. They are illustrated
in Figure 6.2.

TABLE 6.2. Action of D9 on the Necklaces

Type of Element, Number, s, of
g ∈ D9 |Fix g| s · |Fix g|
Order of g Such Elements

Identity 1 1 84 84
Re¬‚ection about a line 2 9 4 36
Rotation through 2π/3 or 4π/3 3 2 3 6
Other rotations 9 6 0 0
= 126



7 4


Figure 6.1. D9 acting on the necklace.

Figure 6.2. Seven types of necklaces.

5 6
“““““““ 4 1 ““““
3 2

Figure 6.3. Benzene ring.

TABLE 6.3. Action of D6 on the Compounds

Type of Element, Number, s, of
g ∈ D6 |Fix g| s · |Fix g|
Order of g Such Elements

Identity 1 1 64
Re¬‚ection in a line through 2 3 48
opposite vertices
[e.g., (26) Ž (35) Ž (1) Ž (4)]
Re¬‚ection in a line through 2 3 24
midpoints of opposite sides
[e.g., (56) Ž (14) Ž (23)]
Rotation through ±π/3 6 2 2 4
[e.g., (123456)]
Rotation through ±2π/3 22
3 2 8
[e.g., (135) Ž (246)]
Rotation through π, 2 1 8
(14) Ž (25) Ž (36)
|D6 | = 12 = 156

Example 6.3. Find the number of different chemical compounds that can be
obtained by attaching CH3 or H radicals to a benzene ring.
Solution. The carbon atoms are placed at the six vertices of a regular hexagon,
and there are 26 ways of attaching CH3 or H radicals. The dihedral group D6
acts on these 26 ways, and we wish to ¬nd the number of orbits.
Consider a re¬‚ection, g, about a line through opposite vertices. The order of
g is 2, and there are three such re¬‚ections, through the three opposite pairs of
vertices. |Fix g| can be determined by looking at Figure 6.3. If a con¬guration is
¬xed by g, the radical in place 2 must be the same as the radical in place 6, and
also the radicals in places 3 and 5 must be equal. Hence the radicals in places 1,
2, 3, and 4 can be chosen arbitrarily, and this can be done in 24 ways.
The number of con¬gurations left ¬xed by each element of D6 is given in
Table 6.3. To check that we have not omitted any elements, we add the column
containing the numbers of elements, and this should equal the order of the group
D6 . It follows from the Burnside theorem that the number of orbits is 156/|D6 | =
156/12 = 13. Hence there are 13 different types of molecules obtainable.


Example 6.4. How many ways is it possible to color the vertices of a cube if n
colors are available?

Solution. If the cube is ¬xed, the eight vertices can each be colored in n ways,
giving a total of n8 colorings. The rotation group of the cube, S4 , permutes these
colorings among themselves, and the number of orbits is the number of distinct
colorings taking the rotations into account. We can calculate the number of orbits
using the Burnside theorem.
There are ¬ve types of elements in the rotation group of the cube. We take an
element g of each type and determine the vertices that must have the same color
in order that the coloring be invariant under g.
Figure 6.4 illustrates the different types of rotations; vertices that have to have
the same color are shaded in the same way. Table 6.4 gives the number of ¬xed
colorings, with column totals.
By the Burnside theorem, the number of orbits and hence the number of
colorings is
|Fix g| = 24 (n8 + 17n4 + 6n2 ).
|S4 | g∈S

p/2 p
g1 g2 g3 g4
Figure 6.4. Types of rotations of the cube.

TABLE 6.4. Colorings of the Vertices of the Cube

|Fix gi |
Type of Number, Number,
Element, gi Order of s, of r, of Choices Which Is
s · |Fix gi |
(Figure 6.4) Such Elements of Colors

n8 n8
Identity 1 1 8
6·1=6 n4 6n4
2 4
4·2=8 n4 8n4
3 4
3·2=6 n2 6n2
4 2
3·1=3 n4 3n4
2 4
|S4 | = 24 n8 + 17n4 + 6n2

This shows, incidentally, that n8 + 17n4 + 6n2 is divisible by 24 for all
n ∈ P.

Example 6.5. In how many ways is it possible to color a regular dodecahedron
so that ¬ve of its faces are black and the other seven are white?

Solution. The number of ways† of choosing ¬ve faces of a ¬xed dodecahedron
12 · 11 · 10 · 9 · 8
= = 792.
to be colored black is
5 5!
The different types of elements in the rotation group, A5 , of the dodecahedron
are shown in Figure 6.5. The numbers of elements of a given type, in Table 6.5,
are calculated as follows. An element of order 3 is a rotation about an axis
through opposite vertices. Since there are 20 vertices, there are ten such axes.
There are two nonidentity rotations of order 3 about each axis; thus the total
number of elements of order 3 is 10 · 2 = 20. The elements of orders 2 and 5
can be counted in a similar way.
If g2 ∈ A5 is of order 3, we can calculate |Fix g2 | as follows. The element
g2 does not ¬x any face and permutes the faces in disjoint 3-cycles. Now ¬ve
black faces cannot be permuted by disjoint 3-cycles without ¬xing two faces, so
|Fix g2 | = 0. Similarly, |Fix g1 | = 0 if g1 is a 2-cycle. If g3 is of order 5, then
g3 is a rotation about an axis through the centers of two opposite faces, and these
two faces are ¬xed. The other ten faces are permuted in two disjoint 5-cycles;
either of these 5-cycles can be black; thus |Fix g3 | = 2.
It follows from Table 6.5 and from the Burnside theorem that the number of
different colorings is 840/60 = 14.

Any face coloring of the dodecahedron corresponds to a vertex coloring of its
dual, the icosahedron.

n n

A set of n elements has subsets of k n elements where is the binomial
k!(n ’ k)!
k k

g1 g2 g3

Figure 6.5. Types of rotations of a dodecahedron.

TABLE 6.5. Colorings of the Dodecahedron

Type of Element, gi Number, s, of
|Fix gi | s · |Fix gi |
(Figure 6.5) Order of gi Such Elements

Identity 1 1 792 792
2 15 0 0
10 · 2 = 20
3 0 0
6 · 4 = 24
5 2 48
|A5 | = 60 = 840


The Burnside theorem can still be applied when the sets to be enumerated do not
have any geometric symmetry. In this case, the symmetry group is usually the
full permutation group Sn .
Consider the different switching circuits obtained by using three switches. We
can think of these as black boxes with three binary inputs x1 , x2 , and x3 and one
binary output f (x1 , x2 , x3 ), as in Figure 6.6. Two circuits, f and g, are called
equivalent if there is a permutation π of the variables so that f (x1 , x2 , x3 ) =
g(xπ1 , xπ2 , xπ3 ). Equivalent circuits can be obtained from each other by just
permuting the wires outside the black boxes, as in Figure 6.7.

f(x 1, x 2, x 3)
x2 f

Figure 6.6. Switching circuit.

f f(x 2, x 3, x 1)

Figure 6.7. Permutation of the inputs.

Example 6.6. Find the number of switching circuits using three switches that
are not equivalent under permutations of the inputs.

Solution. There are eight possible inputs using three binary variables and
hence there are 28 = 256 circuits to consider. The symmetric group S3 acts
on these 256 circuits, and we wish to ¬nd the number of different equivalence
classes, that is, the number of orbits.
Table 6.6 lists the number of circuits left ¬xed by the different types of ele-
ments in S3 . For example, if the switching function f (x1 , x2 , x3 ) is ¬xed by
the transposition (12) of the input variables, then f (0, 1, 0) = f (1, 0, 0) and
f (0, 1, 1) = f (1, 0, 1). The values of f for the inputs (0, 0, 0), (0, 0, 1), (0, 1,
0), (0, 1, 1), (1, 1, 0), and (1, 1, 1) can be chosen arbitrarily in 26 ways.
By Burnside™s theorem and Table 6.6, the number of nonequivalent circuits is
480/|S3 | = 480/6 = 80.

However, this number can be reduced further if we allow permutations and
complementation of the three variables. In a circuit consisting of two-state switches,
the variable xi can be complemented by simply reversing each of the switches
controlled by xi . The resulting circuit is just as simple and the cost is the same as
the original one. In transistor networks, we can just permute the input wires and
add NOT gates as in Figure 6.8.
The eight input values of a three-variable switching circuit can be considered
as the vertices of a three-dimensional cube, as shown in Figure 6.9. The six faces
of this cube are de¬ned by the equations x1 = 0, x1 = 1, x2 = 0, x2 = 1, x3 = 0,
x3 = 1. The group that permutes and complements the variables takes each face
to another face and takes opposite faces to opposite faces. Hence the group is the
complete symmetry group, G, of the cube. There is a morphism ψ: G ’ {1, ’1},

TABLE 6.6. Action of S3 on the Inputs of the Switches

Type of Element, Number, s, of
g ∈ S3 |Fix g| s · |Fix g|
Such Elements

28 = 256
Identity 1
3 · 26 = 192
Transposition 3
2 · 24 = 32
3-Cycle 2
|S3 | = 6 480

x1 NOT
′, ′
f f(x 2, x 1 x 3 )
x3 NOT

Figure 6.8. Permutation and complementation of inputs.



010 100

Figure 6.9. Cube of input values.

which sends proper rotations to 1 and improper rotations to ’1; the kernel of ψ
is the group of proper rotations of the cube which, by the morphism theorem,
must be a normal subgroup of index 2. Therefore, the order of G is 2 · 24 = 48.

Example 6.7. Find the number of switching circuits involving three switches
that are nonequivalent under permutation and complementation of the variables.

Solution. Each boolean function in three variables de¬nes a coloring of the
vertices of the cube of input values. A vertex is colored black if the function is
1 for the corresponding input value. It is colored white if the function takes the
value 0 at that input value.
We can represent the complete symmetry group, G, of the cube by means of
permutations of the vertices labeled 0, 1, 2, 3, 4, 5, 6, 7 in Figure 6.10. Since
the group of proper rotations of the cube is a normal subgroup of index 2 in G,
every element of G can be written as a proper rotation π or as π Ž ρ, where ρ is
the re¬‚ection of the cube in its center.
There are 28 different switching functions of three variables, and Table 6.7
describes the number of circuits that are ¬xed by the action of each element
of the group G on the eight inputs. For example, consider the element g =
(01) Ž (67) Ž (34) Ž (25). If a switching function f is ¬xed under the action of g,
then the images of the input values corresponding to the vertices 0 and 1 must be
the same; that is, f (0, 0, 0) = f (0, 0, 1). Similarly, the images of the input values
corresponding to the vertices 6 and 7 are the same, and f (1, 1, 0) = f (1, 1, 1).


3 6
1 4

Figure 6.10. Labeling of the cube.

TABLE 6.7. Symmetries of a Cube Acting on the Three-Variable
Switching Functions

Type of Element,
g, in the Symmetry Number, s, of
Order of g Such Elements |Fix g| s · |Fix g|
Group of the Cube

Proper rotations
Identity 1 1 256
Rotation about a line joining 2 6 96
midpoints of opposite edges
[e.g., (01) Ž (67) Ž (34) Ž (25)]
Rotation about a line joining 3 8 128
opposite vertices
[e.g., (124) Ž (365) Ž (0) Ž (7)]
Rotation about a line joining centers 4 6 24
of opposite faces
[e.g., (0264) Ž (1375)]
Rotation about a line joining centers 2 3 48
of opposite faces
[e.g., (06) Ž (24) Ž (17) Ž (35)]
Improper rotations
Re¬‚ection in the center 2 1 16
[ρ = (07) Ž (16) Ž (25) Ž (34)]
Re¬‚ection in a diagonal plane 2 6 384
[e.g., (01) Ž (67) Ž (34) Ž (25) Ž ρ =
(06) Ž (17) Ž (2) Ž (3) Ž (4) Ž (5)]
Re¬‚ection and rotation 6 8 32
[e.g., (124) Ž (365) Ž ρ =
(07) Ž (154623)]
Re¬‚ection and rotation 4 6 24
[e.g., (0264) Ž (1375) Ž ρ =
(0563) Ž (1472)]
Re¬‚ection in a central plane 2 3 48
[e.g., (06) Ž (24) Ž (17) Ž (35) Ž ρ =
(01) Ž (23) Ž (45) Ž (67)]
|G| = 48 1056

Also, f (0, 1, 1) = f (1, 0, 0) and f (0, 1, 0) = f (1, 0, 1). Hence the values of
f (0, 0, 0), f (1, 1, 0), f (0, 1, 1), and f (0, 1, 0) can be chosen arbitrarily in 24
ways, and |Fix g| = 24 . In general, if the function f is ¬xed under g, the images
of the input values, corresponding to the vertices in any one cycle of g, must be
the same. Hence |Fix g| is 2r , where r is the number of disjoint cycles in the
permutation representation of g.
It follows from Table 6.7 and the Burnside theorem that the number of non-
equivalent circuits is 1056/|G| = 1056/48 = 22.

TABLE 6.8. Number of Types of Switching Functions

Number of Switches, n 1 2 3 4 5

Number of boolean 4 16 256 65,536 4,294,967,296
functions, 22
Nonequivalent functions 4 12 80 3,984 37,333,248
under permutations of
Nonequivalent functions 3 6 22 402 1,228,158
under permutation and
complementation of
Nonequivalent functions 2 4 14 222 616,126
under permutation and
complementation of
inputs and outputs

We can reduce this number slightly more by complementing the function as
well as the variables; this corresponds to adding a NOT gate to the output. The
group acting is now a combination of a cyclic group of order 2 with the complete
symmetry groups of the cube.
The numbers of nonequivalent circuits for ¬ve or fewer switches given in
Table 6.8 can be computed as in Example 6.7.
In 1951, the Harvard Computing Laboratory laboriously calculated all the
nonequivalent circuits using four switches and the best way to design each of
them. It was not until later that it was realized that the P´ lya theory could be
applied to this problem.
In many examples, it is quite dif¬cult to calculate |Fix g| for every element
g of the group G. P´ lya™s most important contribution to this theory of enumer-
ation was to show how |Fix g| can be calculated, using what are called cycle
index polynomials. This saves much individual calculation, and the results on
nonequivalent boolean functions in Table 6.8 can easily be calculated. However,
it is still a valuable exercise to tackle a few enumeration problems without using
cycle index polynomials, since this gives a better understanding of the P´ lyao
theory. For example, we see in Tables 6.3, 6.4, and 6.7 that |Fix g| is always of
the form nr , where r is the number of disjoint cycles in g.
Further information on the P´ lya theory can be obtained from Biggs [15], Lidl
and Pilz [10], or Stone [22].


Find the number of different types of circular necklaces that could be made from
the sets of beads described in Exercises 6.1 to 6.4, assuming that all the beads
are used on one necklace.
6.1. Three black and three white beads.
6.2. Four black, three white, and one red bead.
6.3. Seven black and ¬ve white beads.
6.4. Five black, six white, and three red beads.
6.5. How many different circular necklaces containing ten beads can be made
using beads of at most two colors?
6.6. Five neutral members and two members from each of two warring factions
are to be seated around a circular armistice table. In how many nonequiv-
alent ways, under the action of D9 , can they be seated if no two members
of opposing factions sit next to each other?
6.7. How many different chemical compounds can be made by attaching H,
CH3 , C2 H5 , or Cl radicals to the four bonds of a carbon atom? The radicals
lie at the vertices of a regular tetrahedron, and the group is the tetrahedral
group A4 .
6.8. How many different chemical compounds can be made by attaching H,
CH3 , or OH radicals to each of the carbon atoms in the benzene ring of
Figure 6.3? (Assume that all of the C“C bonds in the ring are equivalent.)
6.9. How many ways can the vertices of a cube be colored using, at most,
three colors?
6.10. How many ways can the vertices of a regular tetrahedron be colored using,
at most, n colors?
6.11. How many different tetrahedra can be made from n types of resistors when
each edge contains one resistor?
6.12. How many ways can the faces of a regular dodecahedron be colored using,
at most, n colors?
Find the number of different colorings of the faces of the solids described in
Exercises 6.13 to 6.16.
6.13. A regular tetrahedron with two white faces and two black faces.
6.14. A cube with two white, one black, and three red faces.
6.15. A regular icosahedron with four black faces and 16 white faces.
6.16. A regular dodecahedron with ¬ve black faces, two white faces, and ¬ve
green faces.
6.17. How many ways can the faces of a cube be colored with six different
colors, if all the faces are to be a different color?
6.18. (a) Find the number of binary relations, on a set with four elements, that
are not equivalent under permutations of the four elements.


Input plug Switching

Figure 6.11 Figure 6.12

(b) Find the number of equivalence relations, on a set with four elements,
that are not equivalent under permutations of the four elements.
6.19. How many different patchwork quilts, four patches long and three patches
wide, can be made from ¬ve red and seven blue squares, assuming that the
quilts cannot be turned over?
6.20. If the quilts in Exercise 6.19 could be turned over, how many different
patterns are possible?
6.21. Find the number of ways of distributing three blue balls, two red balls, and
four green balls into three piles.
6.22. If the cyclic group Cn , generated by g, operates on a set S, show that the
number of orbits is
|Fix g n/d | · φ(d),
n d/n

where the Euler φ-function, φ(d), is the number of integers from 1 to d
that are relatively prime to d. (See Exercises 4.55 and 4.56.)
6.23. Some transistor switching devices are sealed in a can with three input
sockets at the vertices of an equilateral triangle. The three input wires
are connected to a plug that will ¬t into the input sockets as shown in
Figure 6.11. How many different cans are needed to produce any boolean
function of three input variables?
6.24. How many different ways can the elements of the poset in Figure 6.12 be
colored using, at most, n colors?
6.25. Verify that the number of nonequivalent switching functions of four vari-
ables, under permutation of the inputs, is 3984.

For many purposes, a group is too restrictive an algebraic concept, and we need
a more general object. In the theory of machines, or automata theory, and in
the mathematical study of languages and programming, algebraic objects arise
naturally that have a single binary operation that is associative and has an iden-
tity. These are called monoids. The instructions to a digital machine consist of
a sequence of input symbols that is fed into the machine. Two such sequences
can be combined by following one by the other and, since this operation is asso-
ciative, these input sequences form a monoid; the identity is the empty sequence
that leaves the machine alone. Even though inverses do not necessarily exist in
monoids, many of the general notions from group theory can be applied to these
objects; for example, we can de¬ne subobjects, morphisms, and quotient objects.


A monoid (M, ) consists of a set M together with a binary operation on M
such that

(i) a (b c) = (a b) c for all a, b, c ∈ M. (associativity)
(ii) There exists an identity e ∈ M such that a e = e a = a for all a ∈ M.

All groups are monoids. However, more general objects such as (N, +) and
(N, ·), which do not have inverses, are also monoids.
A monoid (M, ) is called commutative if the operation is commutative.
The algebraic objects (N, +), (N, ·), (Z, +), (Z, ·), (Q, +), (Q, ·), (R, +), (R, ·),
(C, +), (C, ·), (Zn , +), and (Zn , ·) are all commutative monoids.
However, (Z, ’) is not a monoid because subtraction is not associative. In
general, (a ’ b) ’ c = a ’ (b ’ c).
Sometimes an algebraic object would be a monoid but for the fact that it lacks
an identity element; such an object is called a semigroup. Hence a semigroup

Modern Algebra with Applications, Second Edition, by William J. Gilbert and W. Keith Nicholson
ISBN 0-471-41451-4 Copyright ™ 2004 John Wiley & Sons, Inc.


(S, ) is just a set S together with an associative binary operation, . For example,
(P, +) is a semigroup, but not a monoid, because the set of positive integers, P,
does not contain zero.
Just as one of the basic examples of a group consists of the permutations of
any set, a basic example of a monoid is the set of transformations of any set. A
transformation is just a function (not necessarily a bijection) from a set to itself.
In fact, the analogue of Cayley™s theorem holds for monoids, and it can be shown
that every monoid can be represented as a transformation monoid.

Proposition 7.1. Let X be any set and let XX = {f : X ’ X} be the set of all
functions from X to itself. Then (XX , Ž ) is a monoid, called the transformation
monoid of X.

Proof. If f, g ∈ XX , then the composition f Ž g ∈ XX . Composition of func-
tions is always associative, because if f, g, h ∈ XX , then

(f Ž (g Ž h))(x) = f (g(h(x))) and ((f Ž g) Ž h)(x) = f (g(h(x)))

for all x ∈ X. The identity function 1X : X ’ X de¬ned by 1X (x) = x is the
identity for composition. Hence (XX , Ž ) is a monoid.

Example 7.2. If X = {0, 1}, write out the table for the transformation monoid
(XX , Ž ).

Solution. XX has four elements, e, f, g, h, de¬ned as follows.

e(0) = 0 f (0) = 0 g(0) = 1 h(0) = 1
e(1) = 1 f (1) = 0 g(1) = 0 h(1) = 1

The table for (XX , Ž ) is shown in Table 7.1. For example, g Ž f (0) = g(f (0)) =
g(0) = 1, and g Ž f (1) = g(f (1)) = g(0) = 1. Therefore, g Ž f = h. The other
compositions can be calculated in a similar manner.

Example 7.3. Prove that (Z, ) is a commutative monoid, where x y =
6 ’ 2x ’ 2y + xy for x, y ∈ Z.

TABLE 7.1. Transformation Monoid of {0, 1}
e f g h

e e f g h
f f f f f
g g h e f
h h h h h

Solution. For any x, y ∈ Z, x y ∈ Z, and x y = y x, so that is a com-
mutative binary operation on Z. Now

x (y z) = x (6 ’ 2y ’ 2z + yz) = 6 ’ 2x + (’2 + x)(6 ’ 2y ’ 2z + yz)
= ’6 + 4x + 4y + 4z ’ 2xy ’ 2xz ’ 2yz + xyz.


(x y) z = (6 ’ 2x ’ 2y + xy) z = 6 + (’2 + z)(6 ’ 2x ’ 2y + xy) ’ 2z
= ’6 + 4x + 4y + 4z ’ 2xy ’ 2xz ’ 2yz + xyz
= x (y z).

Hence is associative.
Suppose that e x = x. Then 6 ’ 2e ’ 2x + ex = x, and 6 ’ 2e ’ 3x + ex =
0. This implies that (x ’ 2)(e ’ 3) = 0. Hence e x = x for all x ∈ Z if and only
if e = 3. Therefore, (Z, ) is a commutative monoid with 3 as the identity.

Since the operation in a monoid, (M, ), is associative, we can omit the paren-
theses when writing down a string of symbols combined by . We write the
element x1 (x2 x3 ) = (x1 x2 ) x3 simply as x1 x2 x3 .
In any monoid (M, ) with identity e, the powers of any element a ∈ M are
de¬ned by

a 0 = e, a 1 = a, a 2 = a a, a n = a a n’1 for n ∈ N.

The monoid (M, ) is said to be generated by the subset A if every element of
M can be written as a ¬nite combination of the powers of elements of A. That
is, each element m ∈ M can be written as
r r
m = a11 · · · ann for some a1 , a2 , . . . , an ∈ A.

For example, the monoid (P, ·) is generated by all the prime numbers. The
monoid (N, +) is generated by the single element 1, since each element can be
written as the sum of n copies of 1, where n ∈ N. A monoid generated by one
element is called a cyclic monoid.
A ¬nite cyclic group is also a cyclic monoid. However, the in¬nite cyclic
group (Z, +) is not a cyclic monoid; it needs at least two elements to gener-
ate it, for example, 1 and ’1. Not all ¬nite cyclic monoids are groups. For
example, extending the notation of Chapter 3, let σ = ∈ XX
where X = {1, 2, 3, 4}. Then M = {µ, σ, σ 2 , σ 3 } is a cyclic monoid that is not a
group because σ 4 = σ 2 . More generally, the points in Figure 7.1 correspond to
the elements of a cyclic monoid, and the arrows correspond to multiplication by
the element c.

c2 c3
e c
ck + 1
ck ’ m ’ 1

ck + 2
ck + m ’ 2

Figure 7.1. Finite cyclic monoid.

A computer receives its information from an input terminal that feeds in a
sequence of symbols, usually binary digits consisting of 0™s and 1™s. If one
sequence is fed in after another, the computer receives one long sequence that is
the concatenation (or juxtaposition) of the two sequences. These input sequences
together with the binary operation of concatenation form a monoid that is called
the free monoid generated by the input symbols.
Let A be any set (sometimes called the alphabet), and let An be the set
of n-tuples of elements in A. In this chapter, we write an n-tuple as a string
of elements of A without any symbols between them. The elements of An are
called words of length n from A. A word of length 0 is an empty string; this
empty word is denoted by . For example, if A = {a, b}, then baabbaba ∈ A8 ,
A0 = { }, and
A3 = {aaa, aab, aba, abb, baa, bab, bba, bbb}.

Let FM(A) denote the set of all words from A, more formally

FM(A) = A ∪ A ∪ A ∪ A ∪ · · · =
0 2 3
An .

Then (FM(A), ) is called the free monoid generated by A, where the operation
is concatenation, and the identity is the empty word . Another common
notation for FM(A) is A— .
If we do not include the empty word, , we obtain the free semigroup
generated by A; this is often denoted by A+ .
If ± and β are words of length m and n, then ± β is the word of length
m + n obtained by placing ± to the left of β.
If A consists of a single element, a, then the monoid FM(A) =
{ , a, aa, aaa, aaaa, . . .} and, for example, aaa aa = aaaaa. This free monoid,
generated by one element, is commutative.
If A = {0, 1}, then FM(A) consists of all the ¬nite sequences of 0™s and 1™s,

FM(A) = { , 0, 1, 00, 01, 10, 11, 000, 001, . . .}.

We have 010 1110 = 0101110 and 1110 010 = 1110010, so FM(A) is not

If A = {a, b, c, d, . . . , y, z, , .}, the letters of the alphabet together with a
space, , and a period, then

the sky ∈ FM(A) and the sky is b lue. = the sky is blue.

Of course, any nonsense string of letters is also in FM(A); for example,
pqb.a .. xxu ∈ FM(A).
There is an important theorem that characterizes free monoids in terms of
monoid morphisms. If (M, ) and (N, ·) are two monoids, with identities eM
and eN , respectively, then the function f : M ’ N is a monoid morphism from
(M, ) to (N, ·) if

(i) f (x y) = f (x) · f (y) for all x, y ∈ M.
(ii) f (eM ) = eN .

A monoid isomorphism is simply a bijective monoid morphism.
For example, f : (N, +) ’ (P, ·) de¬ned by f (n) = 2n is a monoid mor-
phism because

f (n + m) = 2n+m = 2n · 2m = f (n) · f (m) for all m, n ∈ N.

However, f : N ’ N de¬ned by f (x) = x 2 is not a monoid morphism from
(N, +) to (N, +). We have f (x + y) = (x + y)2 , whereas f (x) + f (y) = x 2 +
y 2 . Hence f (1 + 1) = 4, whereas f (1) + f (1) = 2.

Theorem 7.4. Let (FM(A), ) be the free monoid generated by A and let i: A ’
FM(A) be the function that maps each element a of A into the corresponding
word of length 1, so that i(a) = a.
Then if l: A ’ M is any function into the underlying set of any monoid (M, ·),
there is a unique monoid morphism h: (FM(A), ) ’ (M, ·) such that h Ž i = l.
This is illustrated in Figure 7.2.

Proof. If h satis¬es h Ž i = l, then h must be de¬ned on words of length 1 by
h(a) = l(a). Once a morphism has been de¬ned on its generators, it is determined
completely as follows. Let ± be a word of length n 2 in FM(A). Write ± as
β c, where β is of length n ’ 1 and c is of length 1. Then we have
h(±) = h(β c) = h(β) · h(c) = h(β) · l(c). Hence h can be determined by using
induction on the word length. In fact, if ± = a1 a2 · · · an , where ai ∈ A, then
h(±) = l(a1 ) · l(a2 ) . . . l(an ). Finally, let h( ) be the identity of M.


l h

Figure 7.2. The function l factors through the free monoid FM(A).


We now look at mathematical models of sequential machines. These are machines
that accept a ¬nite set of inputs in sequential order. At any one time, the machine
can be in one of a ¬nite set of internal con¬gurations or states. There may be
a ¬nite set of outputs. These outputs and internal states depend not only on the
previous input but also on the stored information in the machine, that is, on the
previous state of the machine. A pushbutton elevator is an example of such a
machine. A digital computer is a very complex ¬nite-state machine. It can be
broken down into its component parts, each of which is also a machine. The
RS and JK ¬‚ip-¬‚ops, discussed in Exercises 2.69 and 2.70, are examples of two
widely used components.
For simplicity, we only consider machines with a ¬nite set of inputs and a
¬nite set of states. We do not mention any outputs explicitly, because the state set
can be enlarged, if necessary, to include any outputs. The states can be arranged
so that a particular state always gives rise to a certain output.
A ¬nite-state machine, (S, I, m) consists of a set of states S = {s1 , s2 , . . . , sn },
a set of input values I = {i1 , i2 , . . . , it }, and a transition function

m: I — S ’ S,

which describes how each input value changes the states. If the machine is in
state sp and an input iq is applied, the machine will change to state m(iq , sp ).
For example, consider a pushbutton elevator that travels between two levels,
1 and 2, and stops at the lower level 1 when not in use. We take the time for the
elevator to travel from one level to the other to be the basic time interval, and
the controlling machine can change states at the end of each interval. We allow
the machine three inputs, so that I = {0, 1, 2}.
0 if no button is pressed in the preceding time interval

1 if button 1 only is pressed in the preceding time interval
input =
2 if button 2 or both buttons are pressed

in the preceding time interval.

Since the elevator is to stop at the bottom when not in use, we only consider
states that end with the elevator going down. Let the set of states be

S = {stop, down, up“down, down“up“down}.

For example, in the “up“down” state, the elevator is traveling up, but must
remember to come down. If no button is pressed or just button 1 is pressed while it
is going up, the machine will revert to the “down” state when the elevator reaches
level 2. On the other hand, if someone arrives at level 1 and presses button 2, the
machine will change to the “down“up“down” state when the elevator reaches
level 2.

1, 2
Down Up-down Down-up-down
0, 1 0, 1, 2
1, 2
Stop 0

Figure 7.3. State diagram of the elevator.

The machine can be pictured by the state diagram in Figure 7.3. If the input i
causes the machine to change from state sp to state sq , we draw an arrow labeled
i from sp to sq in the diagram.
As another example, consider the following machine that checks the parity
of the number of 1™s fed into it. The set of states is S = {start, even, odd}, and
the set of input values is I = {0, 1}. The function m: I — S ’ S is described by
Table 7.2, and the state diagram is given in Figure 7.4. If any sequence of 0™s
and 1™s is fed into this machine, it will be in the even state if there is an even
number of 1s in the sequence, and in an odd state otherwise.
Let I be the set of input values for any ¬nite-state machine with state set S
and function m: I — S ’ S. Each input value de¬nes a function from the set of
states to itself, the image of any state being the subsequent state produced by the
given input. Hence we have a function

m: I ’ S S ,

where S S is the set of functions from S to itself, and m(i): S ’ S is de¬ned by
[m(i)](s) = m(i, s).

TABLE 7.2. Transition Function
of the Parity Checker
Next State
State 0 1
Start Even Odd
Even Even Odd
Odd Odd Even

Even Odd
0 1 0
0 1

Figure 7.4. State diagram of the parity checker.

i1 i2 i3 ir Machine
• • •

Figure 7.5. Input sequence being fed into a machine.

Any set of input values can be fed into the machine in sequence. The set
of all such input sequences is the underlying set of the free monoid of input
values, FM(I ). By Theorem 7.4, the function m: I ’ S S can be extended to a
monoid morphism
h: (FM(I ), ) ’ (S S , Ž ),

where h(i1 i2 . . . ir ) = m(i1 ) Ž m(i2 ) Ž · · · Ž m(ir ). Note that the input value ir is fed
˜ ˜ ˜
into the machine ¬rst, and we can visualize this feeding of the input sequence
in Figure 7.5. (The reader should be aware that many authors use the opposite
convention in which the left input is fed into the machine ¬rst.)
For example, in the machine that checks the parity of the number of 1s in a
sequence, the state set is S = {start, even, odd} with functions

m: {0, 1} ’ S S
˜ and h: FM({0, 1}) ’ S S .

The morphism h is de¬ned by
˜ if the sequence contains an

 even number of 1™s
h(sequence) = m(1)
˜ if the sequence contains an

 odd number of 1™s

identity function on S if the sequence is empty.


We have seen that different input sequences may have the same effect on a
machine. For example, in the machine that checks the parity of the number of
1™s in a sequence,

h(0101101) = h(0000) = h(11) = h(0);

thus the sequences 0101101, 0000, 11, and 0 cannot be distinguished by the
In any machine with n states, the input sequences can have at most |S S | = nn
different effects. Since there are an in¬nite number of sequences in FM(I ), there
must always be many different input sequences that have the same effect.
The effect that an input has on a ¬nite-state machine de¬nes an equivalence
relation on the input monoid FM(I ). The monoid of a machine will be the quotient

monoid of FM(I ) by this relation. It will always be a ¬nite monoid with, at most,
nn elements. We ¬rst de¬ne the notion of a quotient monoid.
Suppose that R is an equivalence relation on a monoid (M, ). Then R is
called a congruence relation on M if aRb implies that (a c)R(b c) and
(c a)R(c b) for all c ∈ M. The congruence class containing the element
a ∈ M is the set
[a] = {x ∈ M|xRa}.

Proposition 7.5. If R is a congruence relation on the monoid (M, ), the quotient
set M/R = {[a]|a ∈ M} is a monoid under the operation de¬ned by

[a] [b] = [a b].

This monoid is called the quotient monoid of M by R.

Proof. We ¬rst have to verify that the operation is well de¬ned on congruence
classes. Suppose that [a] = [a ] and [b] = [b ] so that aRa and bRb . Then
(a b)R(a b ) and (a b )R(a b ). Since R is transitive, (a b)R(a b ) so
[a b] = [a b ]. This shows that is well de¬ned on M/R. The associativity
of in M/R follows from the associativity of in M. If e is the identity of M,
then [e] is the identity of M/R. Hence (M/R, ) is a monoid.

Let (S, I, m) be a ¬nite-state machine and let the effect of an input sequence
be given by
h: FM(I ) ’ S S .

De¬ne the relation R on FM(I ) by

h(±) = h(β).
if and only if

This is easily veri¬ed to be an equivalence relation. Furthermore, it is a congru-
ence relation on the free monoid (FM(I ), ), because if ±Rβ, then h(±) = h(β),
and h(± γ ) = h(±) Ž h(γ ) = h(β) Ž h(γ ) = h(β γ ); thus (± γ )R(β γ ), and
similarly, (γ ±)R(γ β).
The quotient monoid (FM(I )/R, ) is called the monoid of the machine
(S, I, m).
We can apply the same construction to the free semigroup of input sequences
to obtain the semigroup of the machine.
The monoid of a machine re¬‚ects the capability of the machine to respond
to the input sequences. There are an in¬nite number of sequences in FM(I ),
whereas the number of elements in the quotient monoid is less than or equal to
nn . Two sequences are in the same congruence class if and only if they have the
same effect on the machine.
A morphism theorem for monoids can be proved in a similar way to the
morphism theorem for groups (Theorem 4.25; see Exercise 7.24). Applying this

to the monoid morphism h: FM(I ) ’ S S , it follows that the quotient monoid
FM(I )/R is isomorphic to Im h. This isomorphism assigns to each congruence
class a unique transition between states.

Example 7.6. Draw the state diagram and ¬nd the monoid of the following
machine (S, I, m). The machine has two states, s0 and s1 , and two input sym-
bols, 0 and 1. The effects of the input symbols are given by the functions
h(0), h(1): S ’ S, de¬ned in Table 7.3.

Solution. Let us calculate the effect of inputs of length 2. We have h(ij ) =
h(i) Ž h(j ), where j is fed into the machine ¬rst. It follows from Tables 7.3
and 7.4 that h(00) = h(01) = h(0) and [00] = [01] = [0] in the monoid of the
machine. There are only four functions from {s0 , s1 } to {s0 , s1 }, and these are
h(0), h(1), h(10), and h(11). Hence the monoid of the machine consists of the
four congruence classes [0], [1], [10], and [11]. The table of this quotient monoid
is given in Table 7.5, and the state diagram is given in Figure 7.6. For example,

Next State
State h(0) h(1)
s0 s0 s1
s1 s0 s0

End State
State h(00) h(01) h(10) h(11)
s0 s0 s0 s1 s0
s1 s0 s0 s1 s1

TABLE 7.5. Monoid of the Machine
[0] [1] [10] [11]
[0] [0] [0] [0] [0]
[1] [10] [11] [0] [1]
[10] [10] [10] [10] [10]
[11] [0] [1] [10] [11]

s0 s1
0, 1
Figure 7.6. State diagram.

[1] [10] = [110]. Since h(110)(s0 ) = s0 and h(110)(s1 ) = s0 , it follows that
[110] = [0]. Notice that [11] is the identity; thus, in the monoid of the machine,
[ ] = [11].

Example 7.7. Describe the monoid of the machine ({start, even, odd}, {0, 1}, m)
that determines the parity of the number of 1™s in the input.

Solution. We have already seen that any input sequence with an even number
of 1™s has the same effect as 0 and that any sequence with an odd number of
1™s has the same effect as 1. It follows from Table 7.6 that the monoid of the
machine contains the three elements [ ], [0], and [1]. The table for this monoid
is given in Table 7.7.

Finite-state machines can easily be designed to recognize certain types of input
sequences. For example, most numbers inside a computer are in binary form and
have a check digit attached to them so that there is always an even number of
1™s in each sequence. This is used to detect any machine errors (see Chapter 14).
A ¬nite-state machine like Example 7.7 can be used to perform a parity check
on all the sequences of numbers in the computer. The machine can be designed
to signal a parity check error whenever it ends in the “odd” state.
Let us now look at a machine that will recognize the pattern 010 in any binary
input sequence that is fed into the machine. Figure 7.7 is the state diagram of
such a machine. If the machine is initiated in state s1 , it will be in state s4 if and
only if the preceding inputs were 010, and in this case, the machine sends an
output signal.
This machine has four states; thus the total possible number of different func-
tions between states is 44 = 256. Table 7.8 shows that the input sequences of
length 0, 1, and 2 all have different effects on the various states. However, seven
of the eight sequences of length 3 have the same effect as sequences of length

Next State
State h( ) h(0) h(1)
Start Start Even Odd
Even Even Even Odd
Odd Odd Odd Even

TABLE 7.7. Monoid of the Parity Checker Machine
[] [0] [1]
[] [] [0] [1]
[0] [0] [0] [1]
[1] [1] [1] [0]

0 1 1
1 Sends an
1 0
0 s4
s1 s3
s2 output signal

Figure 7.7. State diagram of a machine that recognizes the sequence 010.

TABLE 7.8. Effects of the Input Sequences on the States of the Machine
End State
State 0 1 00 01 10 11 000 001 010 011 100 101 110 111 0010 1010
s1 s1 s2 s1 s2 s2 s3 s1 s2 s2 s4 s2 s3 s3 s1 s1 s2 s3
s2 s2 s2 s3 s2 s4 s3 s1 s2 s2 s4 s2 s3 s3 s1 s1 s2 s3
s3 s3 s4 s1 s2 s2 s3 s1 s2 s2 s4 s2 s3 s3 s1 s1 s2 s3
s4 s4 s2 s3 s2 s4 s3 s1 s2 s2 s4 s2 s3 s3 s1 s1 s2 s3

0010 1010

000 100 001
010 110 101 011 111

00 01
10 11

0 1


Figure 7.8. Tree diagram of input sequences.

2. The only input sequence with a different effect is 010, the sequence that the
machine is designed to recognize. Therefore, the only sequences of length 4 that
we check are those whose initial inputs are 010, namely, 0010 and 1010.
We can use the tree diagram in Figure 7.8 to check that we have covered all the
possible transition functions obtainable by any input sequence. We label the nodes
of the tree by input sequences. At any node ±, there will be two upward branches
ending in the nodes 0 ± and 1 ±, corresponding to the two input symbols. We
prune the tree at node ±, if ± gives rise to the same transition function as another

TABLE 7.9. Monoid of the Machine That Recognizes 010
[] [0] [1] [00] [01] [10] [11] [010]
[] [] [0] [1] [00] [01] [10] [11] [010]
[0] [0] [00] [01] [00] [00] [010] [00] [00]
[1] [1] [10] [11] [10] [10] [11] [11] [10]
[00] [00] [00] [00] [00] [00] [00] [00] [00]
[01] [01] [010] [00] [010] [010] [00] [00] [010]
[10] [10] [10] [10] [10] [10] [10] [10] [10]
[11] [11] [11] [11] [11] [11] [11] [11] [11]
[010] [010] [010] [010] [010] [010] [010] [010] [010]

node β in the tree. The tree must eventually stop growing because there are only
a ¬nite number of transition functions. Every input sequence has the same effect
as one of the solid black nodes in Figure 7.8. These nodes provide a complete
set of representatives for the monoid of the machine.
Therefore, the monoid of the machine that recognizes the sequence 010 con-
tains only eight elements: [ ], [0], [1], [00], [01], [10], [11], and [010], out of a
possible 256 transition functions between states. Its table is given in Table 7.9.
For further reading on the mathematical structure of ¬nite-state machines and
automata see Hopcroft et al. [18], Kolman [20], or Stone [22].


Are the structures described in Exercises 7.1 to 7.13 semigroups or monoids or
neither? Give the identity of each monoid.
7.1. (N, gcd).
7.2. (Z, [), where a[b = a.
7.3. (R, ), where x y = x 2 + y 2 .
(R, ), where x y = 3 x 3 + y 3 .
(Z3 , ’).
(R, | |), where | | is the absolute value.
7.7. (Z, max), where max (m, n) is the larger of m and n.
(Z, ), where x y = x + y + xy.
(S, gcd), where S = {1, 2, 3, 4, 5, 6}.
7.10. (X, max), where X is the set of real-valued functions on the unit interval
[0,1] and if f, g ∈ X, then max (f, g) is the function on X de¬ned by

max(f, g)(x) = max(f (x), g(x)).

7.11. (T , lcm) where T = {1, 2, 4, 5, 10, 20}.

7.12. The set of all relations on a set X, where the composition of two relations
R and S is the relation RS de¬ned by xRSz if and only if for some y ∈ X,
xRy and ySz.
7.13. ({a, b, c}, ), where the table for is given in Table 7.10.

TABLE 7.10
a b c
a a b c
b b a a
c c a a

Write out the tables for the monoids and semigroups described in Exercises 7.14
to 7.17.
(S, gcd), where S = {1, 2, 3, 4, 6, 8, 12, 24}.
(T , gcd), where T = {1, 2, 3, 4}.
(XX , Ž ), where X = {1, 2, 3}.
({e, c, c2 , c3 , c4 }, ·), where multiplication by c is indicated by an arrow in
Figure 7.9.

c2 c3
e c

Figure 7.9

7.18. Find all the commutative monoids on the set S = {e, a, b} with identity e.
7.19. Are all the elements of the free semigroup generated by {0, 1, 2, 3, 4, 5, 6,
7, 8, 9} simply the nonnegative integers written in the base 10?
7.20. A submonoid of a monoid (M, ·) is a subset N of M containing the
identity and such that x · y ∈ N , for all x, y ∈ N . Find all the submonoids
of the monoid given in Exercise 7.17.
7.21. Prove that there is a monoid isomorphism between (FM({a}), ) and (N, +).
7.22. (Representation theorem for monoids) Prove that any monoid (M, ) is
isomorphic to a submonoid of (M M , Ž ). This gives a representation of any
monoid as a monoid of transformations.
7.23. Prove that any cyclic monoid is either isomorphic to (N, +) or is isomor-
phic to a monoid of the form shown in Figure 7.1, for some values of k
and m.
7.24. (Morphism theorem for monoids) Let f : (M, ) ’ (N, ·) be a morphism
of monoids. Let R be the relation on M de¬ned by m1 Rm2 if and only if

f (m1 ) = f (m2 ). Prove that the quotient monoid (M/R, ) is isomorphic
to the submonoid (Imf, ·) of (N, ·). (See Exercise 7.20.)
7.25. An automorphism of a monoid M is an isomorphism from M to itself.
Prove that the set of all automorphisms of a monoid M forms a group
under composition.
7.26. A machine has three states, s1 , s2 , and s3 and two input symbols, ± and β.
The effect of the input symbols on the states is given by Table 7.11. Draw
the state diagram and ¬nd the monoid of this machine.

TABLE 7.11
Next State
State h(±) h(β)
s1 s1 s1
s2 s3 s1
s3 s2 s1

7.27. Prove that every ¬nite monoid is the monoid of some ¬nite-state machine.
For Exercises 7.28 to 7.30, draw state diagrams of machines with the given input
set, I, that will recognize the given sequence.
7.28. 1101, where I = {0, 1}. 7.29. 0101, where I = {0, 1}.
7.30. 2131, where I = {1, 2, 3}.
Which of the relations described in Exercises 7.31 to 7.34 are congruence rela-
tions on the monoid (N, +)? Find the quotient monoid when the relation is a
congruence relation.
7.31. aRb if a ’ b is even. 7.32. aRb if a > b.
7.33. aRb if a = 2r b for some r ∈ Z. 7.34. aRb if 10|(a ’ b).
The machines in Tables 7.12, 7.13, and 7.14 have state set S = {s1 , s2 , s3 } and
input set I = {0 , 1 }.
7.35. Draw the table of the monoid of the machine de¬ned by Table 7.12.

TABLE 7.12
Next State
State h(0) h(1)
s1 s2 s1
s2 s1 s2
s3 s3 s2

7.36. Draw the table of the monoid of the machine de¬ned by Table 7.13.

TABLE 7.13
Next State
State h(0) h(1)
s1 s2 s1
s2 s3 s1
s3 s3 s2

7.37. Find the number of elements in the monoid of the machine de¬ned by
Table 7.14.

TABLE 7.14
Next State
State h(0) h(1)
s1 s2 s1
s2 s3 s3
s3 s1 s1


. 6
( 13)