.

.

.

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 [15], Lidl

o

and Pilz [10], or Stone [22].

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 [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,

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

[0] [1] [10] [11]

[0] [0] [0] [0] [0]

[1] [10] [11] [0] [1]

[10] [10] [10] [10] [10]

[11] [0] [1] [10] [11]

1

s0 s1

0, 1

0

Figure 7.6. State diagram.

QUOTIENT MONOIDS AND THE MONOID OF A MACHINE 147

[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

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

[] [0] [1]

[] [] [0] [1]

[0] [0] [0] [1]

[1] [1] [1] [0]

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

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

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