<< стр. 6(всего 13)СОДЕРЖАНИЕ >>
of G 0
.
.
.
Column в†’ |Stab x|
Sums
Вґ
126 6 POLYAвЂ“BURNSIDE METHOD OF ENUMERATION

NECKLACE PROBLEMS

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
indistinguishable?

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
NECKLACE PROBLEMS 127

1
2
9

3
8

7 4

5
6
g

Figure 6.1. D9 acting on the necklace.

Figure 6.2. Seven types of necklaces.

5 6
C C
вЂ“вЂ“вЂ“вЂ“вЂ“вЂ“вЂ“ 4 1 вЂ“вЂ“вЂ“вЂ“
C C
g
C C
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

26
Identity 1 1 64
24
Reп¬‚ection in a line through 2 3 48
opposite vertices
[e.g., (26) ЕЅ (35) ЕЅ (1) ЕЅ (4)]
23
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)]
23
Rotation through ПЂ, 2 1 8
(14) ЕЅ (25) ЕЅ (36)
|D6 | = 12 = 156
Вґ
128 6 POLYAвЂ“BURNSIDE METHOD OF ENUMERATION

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.

COLORING POLYHEDRA

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
1
|Fix g| = 24 (n8 + 17n4 + 6n2 ).
1
|S4 | gв€€S
4

p
2p/3
p/2 p
g1 g2 g3 g4
Figure 6.4. Types of rotations of the cube.
COLORING POLYHEDRA 129

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 |
nr
(Figure 6.4) Such Elements of Colors
gi

n8 n8
Identity 1 1 8
6В·1=6 n4 6n4
2 4
g1
4В·2=8 n4 8n4
3 4
g2
3В·2=6 n2 6n2
4 2
g3
3В·1=3 n4 3n4
2 4
g4
|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
12
= = 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 n
=
вЂ
A set of n elements has subsets of k n elements where is the binomial
k!(n в€’ k)!
k k
coefп¬Ѓcient.
Вґ
130 6 POLYAвЂ“BURNSIDE METHOD OF ENUMERATION

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
g1
10 В· 2 = 20
3 0 0
g2
6 В· 4 = 24
5 2 48
g3
|A5 | = 60 = 840

COUNTING SWITCHING CIRCUITS

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.

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

Figure 6.6. Switching circuit.

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

Figure 6.7. Permutation of the inputs.
COUNTING SWITCHING CIRCUITS 131

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
28
Identity 1
3 В· 26 = 192
26
Transposition 3
2 В· 24 = 32
24
3-Cycle 2
|S3 | = 6 480

x1 NOT
вЂІ, вЂІ
f f(x 2, x 1 x 3 )
x2
x3 NOT

Figure 6.8. Permutation and complementation of inputs.
Вґ
132 6 POLYAвЂ“BURNSIDE METHOD OF ENUMERATION

111

110
011
101

010 100
001

000
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).

7

3 6
5
2
1 4

0
Figure 6.10. Labeling of the cube.
COUNTING SWITCHING CIRCUITS 133

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
28
Identity 1 1 256
24
Rotation about a line joining 2 6 96
midpoints of opposite edges
[e.g., (01) ЕЅ (67) ЕЅ (34) ЕЅ (25)]
24
Rotation about a line joining 3 8 128
opposite vertices
[e.g., (124) ЕЅ (365) ЕЅ (0) ЕЅ (7)]
22
Rotation about a line joining centers 4 6 24
of opposite faces
[e.g., (0264) ЕЅ (1375)]
24
Rotation about a line joining centers 2 3 48
of opposite faces
[e.g., (06) ЕЅ (24) ЕЅ (17) ЕЅ (35)]
Improper rotations
24
Reп¬‚ection in the center 2 1 16
[ПЃ = (07) ЕЅ (16) ЕЅ (25) ЕЅ (34)]
26
Reп¬‚ection in a diagonal plane 2 6 384
[e.g., (01) ЕЅ (67) ЕЅ (34) ЕЅ (25) ЕЅ ПЃ =
(06) ЕЅ (17) ЕЅ (2) ЕЅ (3) ЕЅ (4) ЕЅ (5)]
22
Reп¬‚ection and rotation 6 8 32
[e.g., (124) ЕЅ (365) ЕЅ ПЃ =
(07) ЕЅ (154623)]
22
Reп¬‚ection and rotation 4 6 24
[e.g., (0264) ЕЅ (1375) ЕЅ ПЃ =
(0563) ЕЅ (1472)]
24
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.
Вґ
134 6 POLYAвЂ“BURNSIDE METHOD OF ENUMERATION

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
n
functions, 22
Nonequivalent functions 4 12 80 3,984 37,333,248
under permutations of
inputs
Nonequivalent functions 3 6 22 402 1,228,158
under permutation and
complementation of
inputs
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
o
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-
o
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 , Lidl
o
and Pilz , or Stone .
EXERCISES 135

EXERCISES

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.
Вґ
136 6 POLYAвЂ“BURNSIDE METHOD OF ENUMERATION

x1
Output
x2
x3

Input plug Switching
device

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
1
|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.
7
MONOIDS AND MACHINES

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.

MONOIDS AND SEMIGROUPS

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.

137
138 7 MONOIDS AND MACHINES

(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
MONOIDS AND SEMIGROUPS 139

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.

Also,

(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.
r
a22

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
1234
example, extending the notation of Chapter 3, let Пѓ = в€€ XX
1143
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.
140 7 MONOIDS AND MACHINES

ck
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 .
n=0

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
commutative.
MONOIDS AND SEMIGROUPS 141

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.

i
A FM(A)

l h
M

Figure 7.2. The function l factors through the free monoid FM(A).
142 7 MONOIDS AND MACHINES

FINITE-STATE MACHINES

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.
FINITE-STATE MACHINES 143

2
1, 2
Down Up-down Down-up-down
0, 1 0, 1, 2
1, 2
0
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
Input
Initial
State 0 1
Start Even Odd
Even Even Odd
Odd Odd Even

1
Even Odd
0 1 0
0 1
Start

Figure 7.4. State diagram of the parity checker.
144 7 MONOIDS AND MACHINES

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
пЈґm(0)
пЈґ
пЈґ
пЈІ 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.

QUOTIENT MONOIDS AND THE MONOID OF A MACHINE

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
machine.
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
QUOTIENT MONOIDS AND THE MONOID OF A MACHINE 145

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
О±RОІ

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
146 7 MONOIDS AND MACHINES

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  =  =  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 , , , and . The table of this quotient monoid
is given in Table 7.5, and the state diagram is given in Figure 7.6. For example,

TABLE 7.3
Next State
Initial
State h(0) h(1)
s0 s0 s1
s1 s0 s0

TABLE 7.4
End State
Initial
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
   
    
    
    
    

1
s0 s1
0, 1
0
Figure 7.6. State diagram.
QUOTIENT MONOIDS AND THE MONOID OF A MACHINE 147

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

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 [ ], , and . 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

TABLE 7.6
Next State
Initial
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
[]  
[] []  
   
   
148 7 MONOIDS AND MACHINES

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

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
Initial
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
EXERCISES 149

TABLE 7.9. Monoid of the Machine That Recognizes 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: [ ], , , , , , , and , 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. , Kolman , or Stone .

EXERCISES

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 .
7.4.
(Z3 , в€’).
7.5.
(R, | |), where | | is the absolute value.
7.6.
7.7. (Z, max), where max (m, n) is the larger of m and n.
(Z, ), where x y = x + y + xy.
7.8.
(S, gcd), where S = {1, 2, 3, 4, 5, 6}.
7.9.
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}.
150 7 MONOIDS AND MACHINES

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}.
7.14.
(T , gcd), where T = {1, 2, 3, 4}.
7.15.
(XX , ЕЅ ), where X = {1, 2, 3}.
7.16.
({e, c, c2 , c3 , c4 }, В·), where multiplication by c is indicated by an arrow in
7.17.
Figure 7.9.

c2 c3
e c

c4
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
EXERCISES 151

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
Initial
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
Initial
State h(0) h(1)
s1 s2 s1
s2 s1 s2
s3 s3 s2
152 7 MONOIDS AND MACHINES

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

TABLE 7.13
Next State
Initial
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
Initial
State h(0) h(1)
s1 s2 s1
s2 s3 s3
s3 s1 s1

 << стр. 6(всего 13)СОДЕРЖАНИЕ >>