. 1
( 9)



>>

This page intentionally left blank
Automata Theory with Modern Applications

Recent applications to biomolecular science and DNA computing have created a new
audience for automata theory and formal languages. This is the only introductory book
to cover such applications. It begins with a clear and readily understood exposition of
the basic principles, that assumes only a background in discrete mathematics. The ¬rst
¬ve chapters give a gentle but rigorous coverage of regular languages and Kleene™s
Theorem, minimal automata and syntactic monoids, Turing machines and decidability,
and explain the relationship between context-free languages and pushdown automata.
They include topics not found in other texts at this level, including codes, retracts, and
semiretracts. The many examples and exercises help to develop the reader™s insight.
Chapter 6 introduces combinatorics on words and then uses it to describe a visually
inspired approach to languages that is a fresh but accessible area of current research.
The ¬nal chapter explains recently-developed language theory coming from
developments in bioscience and DNA computing.

With over 350 exercises (for which solutions are available), plenty of examples and
illustrations, this text will be welcomed by students as a contemporary introduction to
this core subject; others, new to the ¬eld, will appreciate this account for self-learning.
Automata Theory
with Modern Applications
With contributions by Tom Head


JAMES A. ANDERSON
University of South Carolina Upstate
©¤§ µ®©© °
Cambridge, New York, Melbourne, Madrid, Cape Town, Singapore, São Paulo

Cambridge University Press
The Edinburgh Building, Cambridge  µ, UK
Published in the United States of America by Cambridge University Press, New York
www.cambridge.org
Information on this title: www.cambridge.org/9780521848879

© Cambridge University Press 2006


This publication is in copyright. Subject to statutory exception and to the provision of
relevant collective licensing agreements, no reproduction of any part may take place
without the written permission of Cambridge University Press.

First published in print format 2006

©®-± ·-°-µ±±-µ°- eBook (EBL)
©®-±° °-µ±±-µ°- eBook (EBL)

©®-± ·-°-µ±-·- hardback
©®-±° °-µ±-·- hardback

©®-± ·-°-µ±-±- paperback
©®-±° °-µ±-±- paperback

Cambridge University Press has no responsibility for the persistence or accuracy of µ¬s
for external or third-party internet websites referred to in this publication, and does not
guarantee that any content on such websites is, or will remain, accurate or appropriate.
Contents




Preface page vii
1 Introduction 1
1.1 Sets 1
1.2 Relations 6
1.3 Functions 12
1.4 Semigroups 16
2 Languages and codes 23
2.1 Regular languages 23
2.2 Retracts (Optional) 29
2.3 Semiretracts and lattices (Optional) 34
3 Automata 37
3.1 Deterministic and nondeterministic automata 37
3.2 Kleene™s Theorem 52
3.3 Minimal deterministic automata and syntactic monoids 72
3.4 Pumping Lemma for regular languages 84
3.5 Decidability 86
3.6 Pushdown automata 89
3.7 Mealy and Moore machines 99
4 Grammars 114
4.1 Formal grammars 114
4.2 Chomsky normal form and Greibach normal form 138
4.3 Pushdown automata and context-free languages 149
4.4 The Pumping Lemma and decidability 162
5 Turing machines 169
5.1 Deterministic Turing machines 169


v
Contents
vi


5.2 Nondeterministic Turing machines and acceptance of
context-free languages 190
5.3 The halting problem for Turing machines 194
5.4 Undecidability problems for context-free languages 200
6 A visual approach to formal languages 210
6.1 Introduction 210
6.2 A minimal taste of word combinatorics 212
6.3 The spectrum of a word with respect to a language 214
The spectral partition of + and the support of L
6.4 216
6.5 Visualizing languages 217
6.6 The sketch parameters of a language 221
6.7 Flag languages 223
6.8 Additional tools from word combinatorics 224
6.9 Counting primitive words in a regular language 225
6.10 Algorithmic sketching of regular languages 227
7 From biopolymers to formal language theory 231
7.1 Introduction 231
7.2 Constructing new words by splicing together
pairs of existing words 232
7.3 The motivation from molecular biology 233
7.4 Splicing rules, schemes, systems, and languages 236
7.5 Every splicing language is a regular language 239
The syntactic monoid of a regular language L allows
7.6
an effective determination of the set of all splicing
rules that respect L 241
7.7 It is algorithmically decidable whether a given regular
language is a re¬‚exive splicing language 242
Appendix A Cardinality 245
Appendix B Co-compactness Lemma 247

References 249
Further reading 251
Index 253
Preface




This book serves two purposes, the ¬rst is as a text and the second is for
someone wishing to explore topics not found in other automata theory texts.
It was originally written as a text book for anyone seeking to learn the basic
theories of automata, languages, and Turing machines. In the ¬rst ¬ve chapters,
the book presents the necessary basic material for the study of these theories.
Examples of topics included are: regular languages and Kleene™s Theorem;
minimal automata and syntactic monoids; the relationship between context-free
languages and pushdown automata; and Turing machines and decidability. The
exposition is gentle but rigorous, with many examples and exercises (teachers
using the book with their course may obtain a copy of the solution manual by
sending an email to solutions@cambridge.org). It includes topics not found in
other texts such as codes, retracts, and semiretracts.
Thanks primarily to Tom Head, the book has been expanded so that it should
be of interest to people in mathematics, computer science, biology, and possibly
other areas. Thus, the second purpose of the book is to provide material for
someone already familiar with the basic topics mentioned above, but seeking
to explore topics not found in other automata theory books.
The two ¬nal chapters introduce two programs of research not previously
included in beginning expositions. Chapter 6 introduces a visually inspired
approach to languages allowed by the unique representation of each word as a
power of a primitive word. The required elements of the theory of combinatorics
on words are included in the exposition of this chapter. This is an entirely fresh
area of research problems that are accessible on the completion of Chapter 6.
Chapter 7 introduces recently developed language theory that has been inspired
by developments in the biomolecular sciences and DNA computing. Both of
these ¬nal chapters are kept within automata theory through their concentration
on results in regular languages. Research in progress has begun to extend these
concepts to broader classes of languages. There are now specialized books on

vii
Preface
viii


DNA-computing “ and in fact a rapidly growing Springer-Verlag Series on
˜Natural Computing™ is in progress. This book is the ¬rst one to link (introduc-
tory) automata theory into this thriving new area.
Readers with a strong background will probably already be familiar with
the material in Chapter 1. Those seeking to learn the basic theory of automata,
languages, and Turing machines will probably want to read the chapters in order.
The sections on retracts and semiretracts, while providing interesting examples
of regular languages, are not necessary for reading the remainder of the book.
A person already familiar with the basics of automata, languages, and Turing
machines, will probably go directly to Chapters 6 and 7 and possibly the sections
on retracts and semiretracts.
I thank Tom Head for the work he has done on this book including his
contributions of Chapters 6 and 7 as well as other topics. I also thank Brett
Bernstein for his excellent proofreading of an early version of the book and
Kristin and Phil Muzik for creating the ¬gures for the book. Finally I would
like to thank Ken Blake and David Tranah at Cambridge University Press for
their help and support.
1
Introduction




1.1 Sets
Sets form the foundation for mathematics. We shall de¬ne a set to be a well-
de¬ned collection of objects. This de¬nition is similar to the one given by
Georg Cantor, one of the pioneeers in the early development of set theory. The
inadequacy of this de¬nition became apparent when paradoxes or contradictions
were discovered by the Italian logician Burali-Forti in 1879 and later by Bertrand
Russell with the famous Russell paradox. It became obvious that sets had to
be de¬ned more carefully. Axiomatic systems have been developed for set
theory to correct the problems discussed above and hopefully to avoid further
contradictions and paradoxes. These systems include the Zermelo“Fraenkel“
von Neumann system, the G¨ del“Hilbert“Bernays system and the Russell“
o
Whitehead system. In these systems the items that were allowed to be sets were
restricted. Axioms were created to de¬ne sets. Any object which could not be
created from these axioms was not allowed to be a set. These systems have
been shown to be equivalent in the sense that if one system is consistent, then
they all are. However, G¨ del has shown that if the systems are consistent, it is
o
impossible to prove that they are.

De¬nition 1.1 An object in a set is called an element of the set or is said to
belong to the set. If an object x is an element of a set A, this is denoted by
x ∈ A. If an object x is not a member of a set A, this is denoted by x ∈ A.
/

Objects in a set are called elements. Finite sets may be described by listing
their elements. For example the set of positive integers less than or equal to
seven may be described by the notation {1, 2, 3, 4, 5, 6, 7} where the braces
are used to indicate that we are describing a set. Thus symbols in an alphabet can
be listed using this notation. We can also list the set of positive integers less than
or equal to 10 000, by using the notation {1, 2, 3, 4, . . . , 10 000} and the set of

1
Introduction
2


positive integers by {1, 2, 3, 4, . . .}, where three dots denote the continuation of
a pattern. By de¬nition, 1 ∈ {1, 2, 3, 4, 5} but 8 ∈ {1, 2, 3, 4, 5}. An element of
/
a set may also be a set. Therefore A = {1, 2, {3, 4, 5}, 3, 4} is a set that contains
elements 1, 2, {3, 4, 5}, 3, and 4. Note that 5 ∈ A, but {3, 4, 5} ∈ A.
/
In many cases, listing the elements of a set can be tedious if not impossible.
For example, consider listing the set of all primes. We thus have a second form
of notation called set builder notation. Using this notation, the set of all objects
having property P will be described by {x : x has property P}. For example
the set of all former Prime Ministers of Britain would by described by {x : x
has been a Prime Minister of Britain}. The set of all positive even integers less
that or equal to 100, could be described by {x : x is a positive even integer less
than or equal to 100}.

De¬nition 1.2 A set A is called a subset of a set B if every element of the set
A is an element of the set B. If A is a subset of B, this is denoted by A ⊆ B. If
A is not a subset of B, this is denoted by A B.

Therefore {a, b, c} ⊆ {a, b, c, d, e} but {a, b, f } {a, b, c, d, e}. By de¬-
nition, any set is a subset of itself.

De¬nition 1.3 A set A is equal to a set B if A ⊆ B and B ⊆ A.

Therefore two sets are equal if they contain the same elements. Notice that
there is no order in a set. A set is simply de¬ned by the elements that it contains.
Also an element either belongs to a set or does not. It would be redundant to
list an element more than once when de¬ning a set.

De¬nition 1.4 The intersection of two sets A and B, denoted by A © B, is the
set consisting of all elements contained in both A and B.

Let A = {x : x plays tennis} and B = {x : x plays golf}, then A © B = {x :
x plays tennis and golf}. If A = {x : x is a positive integer divisible by 3} and
B = {x : x is a positive integer divisible by 2}, then A © B = {x : x is a positive
integer divisible by 6}.

De¬nition 1.5 The union of two sets A and B, denoted by A ∪ B, is the set
consisting of all elements contained in either A or B.

Let A = {x : x plays tennis} and B = {x : x plays golf}, then A ∪ B = {x :
x plays tennis or golf}.
If A = {x : x is a positive integer divisible by 3} and B = {x : x is a positive
integer divisible by 2}, then A ∪ B = {x : x is a positive integer divisible by
either 2 or 3}.
1.1 Sets 3


De¬nition 1.6 The set difference, denoted by B ’ A, is the set of all elements
in the set B that are not in the set A.

For example, the set {1, 2, 3, 4, 5} ’ {2, 4, 6, 8, 10} = {1, 3, 5}.

Example 1.1 Let A = {x : x plays tennis} and B = {x : x plays golf}, the set
A ’ B = {x : x plays tennis but does not play golf}.

De¬nition 1.7 The symmetric difference, denoted by A B, is the set
(A ’ B) ∪ (B ’ A).

B = (A ∪ B) ’ (A © B).
It is easily seen that A

Example 1.2 Let A = {x : x plays tennis} and B = {x : x plays golf}, the set
A B = {x : x plays tennis or golf but not both}.

We de¬ne two special sets. The ¬rst is the empty set, which is denoted
by … or {}. As the name implies, this set contains no elements. It is a subset
of every set A since every element in the empty set is also in A. The second
special set is the universe or universe of discourse, which we denote by U.
The universe is given, and limits or describes the type of sets under discussion,
since they must all be subsets of the universe. For example if the sets we are
describing are subsets of the integers then the universe could be the set of
integers. If the universe is the the set of college students, then the set {x : x
is a musician} would be the set of all musicians who are in college. Often the
universe is understood and so is not explicitly mentioned. Later we shall see
that the universe of particular interest to us is the set of all strings of symbols
in a given alphabet.

Let A be a set. A = U ’ A is the set of all elements not in A.
De¬nition 1.8

Example 1.3 Let A be the set of even integers and U be the set of integers.
Then A is the set of odd integers.

Example 1.4 Let A = {x : x collects coins}, then A = {x : x does not collect
coins}.

The proof of the following theorem is left to the reader.

Let A, B, and C be subsets of the universal set U
Theorem 1.1

(a) Distributive properties

A © (B ∪ C) = (A © B) ∪ (A © C),
A ∪ (B © C) = (A ∪ B) © (A ∪ C).
Introduction
4


(b) Idempotent properties
A © A = A,
A ∪ A = A.
(c) Double Complement property

(A ) = A.

(d) De Morgan™s laws
(A ∪ B) = A © B ,
(A © B) = A ∪ B .
(e) Commutative properties
A © B = B © A,
A ∪ B = B ∪ A.
(f) Associative laws
A © (B © C) = (A © B) © C,
A ∪ (B ∪ C) = (A ∪ B) ∪ C.
(g) Identity properties
A ∪ … = A,
A © U = A.
(h) Complement properties
A ∪ A = U,
A © A = ….
De¬nition 1.9 The size or cardinality of a ¬nite set A, denoted by |A|, is the
number of elements in the set. An in¬nite set which can be listed so that there is
a ¬rst element, second element, third element etc. is called countably in¬nite.
If it cannot be listed, it is said to be uncountable. Two in¬nite sets have the
same cardinality if there is a one-to-one correspondence between the two sets.
We denote this by |A| = |B|. If there is a one-to-one correspondence between
A and a subset of B, we denote this by |A| ¤ |B|. If |A| ¤ |B| but there is no
one-to-one correspondence between A and B, then we denote this by |A| < |B|.

Thus the cardinality of the set {a, b, c, {d, e, f }} is 4. Intuitively, there is a
one-to-one correspondence between two sets if elements of the two sets can be
written in pairs so that each element in one set can be paired with one and only
one element of the other set. The positive integers are obviously countable.
Although it will not be proved here, the integers and rational numbers are
1.1 Sets 5


both countable sets. The real numbers however are not a countable set. We
see that there are two in¬nite sets, the countable sets and the uncountable sets
with different cardinality; however, we shall soon see that there are an in¬nite
number of in¬nite sets of different cardinality.
Further discussion of cardinality will be continued in the appendices.
De¬nition 1.10 Let A and B be sets. The Cartesian product of A and B,
denoted by A — B is the set {(a, b) : a ∈ A and b ∈ B}.
For example, let A = {a, b} and B = {1, 2, 3}, then
A — B = {(a, 1)(a, 2)(a, 3)(b, 1)(b, 2)(b, 3)}.
The familiar Cartesian plane R — R is the set of all ordered pairs of real numbers.
Note that for ¬nite sets |A — B| = |A| — |B|.
De¬nition 1.11 The power set of a set A, denoted by P(A), is the set of all
subsets of A.
For example the power set of {a, b, c} is
{{a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}, …}.
In the ¬nite case, it can be easily shown that |P(A)| = 2|A| .


Exercises
(1) State which of the following are true and which are false:
(a) {…} ⊆ A for an arbitrary set A.
(b) … ⊆ A for an arbitrary set A.
(c) {a, b, c} ⊆ {a, b, {a, b, c}}.
(d) {a, b, c} ∈ {a, b, {a, b, c}}.
(e) A ∈ P(A).
(2) Prove Theorem 1.1. Let A, B, and C be subsets of the universal set U.
(a) Idempotent property
A © A = A,
A ∪ A = A.
(b) Double Complement property
(A ) = A.
(c) De Morgan™s laws
(A ∪ B) = A © B ,
(A © B) = A ∪ B .
Introduction
6


(d) Commutative properties
A © B = B © A,
A ∪ B = B ∪ A.
(e) Associative properties
A © (B © C) = (A © B) © C,
A ∪ (B ∪ C) = (A ∪ B) ∪ C.

(f) Distributive properties
A © (B ∪ C) = (A © B) ∪ (A © C),
A ∪ (B © C) = (A ∪ B) © (A ∪ C).

(g) Identity properties
A ∪ … = A,
A © U = A.

(h) Complement properties
A ∪ A = U,
A © A = ….
(3) Given a set A ∈ P(C), ¬nd a set B such that A B = ….
(4) If A ⊆ B, what is A B?
(5) Using the properties in Theorem 1.1 prove that A © (B C) =
(A © B) (A © C).
(6) Use induction to prove that for any ¬nite set A, |A| < |P(A)|.
(7) (Russell™s Paradox) Let S be the set of all sets. Then S ∈ S. Obviously
… ∈ …. Let W = {A : A ∈ A}. Discuss whether W ∈ W .
/ /
(8) Prove using the properties in Theorem 1.1
(a) A ’ (B ∪ C) = (A ’ B) © (A ’ C),
(b) A ’ (B © C) = (A ’ B) ∪ (A ’ C).
(9) Use the fact that A © (A ∪ B) = A to prove that A ∪ (A © B) = A.
(10) Prove that if two disjoint sets are countable, then their union is countable.



1.2 Relations
De¬nition 1.12 Given sets A and B, any subset R of A — B is a relation
between A and B. If (a, b) ∈ R, this is often denoted by aRb. If A = B, R is
said to be a relation on A.
1.2 Relations 7


Note that relations need not have any particular property nor even be describ-
able. Obviously we will be interested in those relations which are describable
and have particular properties which will be shown later.
If A = {a, b, c, d, e} and B = {1, 2, 3, 4, 5}, then
Example 1.5
{(a, 3), (a, 2), (c, 2), (d, 4), (e, 4), (e, 5)}
is a relation between A and B.
Example 1.6 {(x, y) : x ≥ y} and {(x, y) : x 2 + y 2 = 4} are relations on R.
Example 1.7 If A is the set of people, then aRb if a and b are cousins is a
relation on A.
De¬nition 1.13 The domain of a relation R between A and B is the set
{a : a ∈ A and there exists b ∈ B so that aRb}. The range of a relation R
between A and B is the set {b : b ∈ B and there exists a ∈ A so that aRb}.
Example 1.8 The domain and range of the relation {(x, y) : x 2 + y 2 = 4} are
’2 ¤ x ¤ 2 and ’2 ¤ y ¤ 2 respectively.
Example 1.9 The relation R is on the set of people. The domain and range
of R is the set of people who have cousins.
De¬nition 1.14 Let R be a relation between A and B. The inverse of the
relation R denoted by R’1 is a relation been B and A, de¬ned by R’1 =
{(b, a) : (a, b) ∈ R}.
Example 1.10 If A = {a, b, c, d, e} and B = {1, 2, 3, 4, 5}, and
R = {(a, 3), (a, 2), (b, 3), (b, 5), (c, 3), (d, 2), (d, 3), (e, 4), (e, 5)}
is a relation between A and B then
R’1 = {(3, a), (2, a), (3, b), (5, b), (3, c), (2, d), (3, d), (4, e), (5, e)}
is a relation between B and A.
If R={(x, y) : y = 4x 2 ), then R’1 ={(y, x) : y = 4x 2 }.
Example 1.11
De¬nition 1.15 Let R be a relation between A and B, and let S be a relation
between B and C. The composition of R and S, denoted by S —¦ R is a relation
between A and C de¬ned by (a, c) ∈ S —¦ R if there exists b ∈ B such that
(a, b) ∈ R and (b, c) ∈ S.
Example 1.12 Let A = {a, b, c, d, e} and B = {1, 2, 3, 4, 5} and
R = {(a, 3), (a, 2), (c, 2), (d, 4), (e, 4), (e, 5)}
Introduction
8


be a relation between A and B. Then, as shown above
R’1 = {(3, a), (2, a), (2, c), (4, d), (4, e), (5, e)}
is a relation between B, and A,
R —¦ R’1 = {(3, 3), (3, 2), (2, 2), (2, 3), (4, 4), (5, 5)}
is a relation on B, and
R’1 —¦ R = {(a, a), (a, c), (c, a), (c, c), (d, d), (d, e), (e, e)}
is a relation on A.
Example 1.13 If R = {(x, y) : y = x + 5} and S = {(y, z) : z = y 2 } then
S —¦ R = {(x, z) : z = (x + 5)2 }.
Theorem 1.2 Composition of relations is associative; that is, if A, B, and C
are sets and if R ⊆ A — B, S ⊆ B — C, and T ⊆ C — D, then T —¦ (S —¦ R) =
(T —¦ S) —¦ R.
Proof First show that T —¦ (S —¦ R) ⊆ (T —¦ S) —¦ R. Let (a, d) ∈ T —¦ (S —¦ R),
then there exists c ∈ C such that (a, c) ∈ S —¦ R and (c, d) ∈ T . Since (a, c) ∈
S —¦ R, there exists b ∈ B so that (a, b) ∈ R and (b, c) ∈ S. Since (b, c) ∈ S
and (c, d) ∈ T , (b, d) ∈ T —¦ S. Since (b, d) ∈ T —¦ S and (a, b) ∈ R, (a, d) ∈
(T —¦ S) —¦ R. Thus, T —¦ (S —¦ R) ⊆ (T —¦ S) —¦ R. The second part of the proof
showing that (T —¦ S) —¦ R ⊆ T —¦ (S —¦ R) is similar and is left to the reader.

When R is a relation on a set A, there are certain special properties that R
may have which we now consider.
De¬nition 1.16 A relation R on A is re¬‚exive if aRa for all a ∈ A. A relation
R on A is symmetric if aRb ’ bRa for all a, b ∈ A. A relation R on A
is antisymmetric if aRb and bRa implies a = b. A relation is transitive if
whenever aRb and bRc, then aRc.
Example 1.14 Let A be the set of all people and aRb if a and b are siblings.
The relation R is not re¬‚exive since a person cannot be their own brother or
sister. It is symmetric however since if a and b are siblings, then b and a are
siblings. It might appear that R is transitive. Such is not the case however since
if a and b are siblings, and b and a are siblings, we must conclude that a and a
are siblings, which we know is not true.
Example 1.15 Let A be the set of all people and aRb if a and b have the
same parents. The relation R is re¬‚exive since everyone has the same parents
as themselves. It is symmetric since if a and b have the same parents, b and
1.2 Relations 9


a have the same parents. It is also transitive since if a and b have the same
parents and b and c have the same parents, then a and c have the same parents.
Let A = {a, b, c, d, e} and
Example 1.16

R = {(a, a), (a, b), (b, c), (b, b), (a, c), (c, c), (d, d), (a, d), (c, e), (d, a), (b, a)}.

R is not re¬‚exive since (e, e) ∈ R. It is not symmetric because (a, c) ∈ R, but
/
(c, a) ∈ R. It is not antisymmetric since (a, d), (d, a) ∈ R, but d = a. It is not
/
transitive since (a, c), (c, e) ∈ R, but (a, e) ∈ R.
/
Example 1.17 Let R be the relation on Z de¬ned by aRb if a ’ b is a multiple
of 5. Certainly a ’ a = 0 is a multiple of 5, so R is re¬‚exive. If a ’ b is a
multiple of 5, then a ’ b = 5k for some integer k. Hence b ’ a = 5(’k) is a
multiple of 5, so R is symmetric. If a ’ b is a multiple of 5 and b ’ c is a
multiple of 5, then a ’ b = 5k and b ’ c = 5m for some integers k and m.
a’c=a’b+b’c
= 5k + 5m
= 5(k + m)
so that a ’ c is a multiple of 5. Hence R is transitive.
De¬nition 1.17 A relation R on A is an equivalence relation if it is re¬‚exive,
symmetric, and transitive.
Example 1.18 Let Z be the set of integers and R1 be the relation on Z de¬ned
by R1 = {(m, n) : m ’ n} is divisible by 5. R1 is shown above to be an equiv-
alence relation on the integers.
Example 1.19 Let A be the set of all people. De¬ne R2 by aR2 b if a and b
are the same age. This is easily shown to be an equivalence relation.
An equivalence relation on a set A divides A into nonempty subsets that are
mutually exclusive or disjoint, meaning that no two of them have an element
in common. In the ¬rst example above, the sets
{. . . ’ 20, ’15, ’10, ’5, 0, 5, 10, 15, 20, . . .}
{. . . ’ 19, ’14, ’9, ’4, 1, 6, 11, 16, 21, . . .}
{. . . ’ 18, ’13, ’8, ’3, 2, 7, 12, 17, 22, . . .}
{. . . ’ 17, ’12, ’7, ’2, 3, 8, 13, 18, 23, . . .}
{. . . ’ 18, ’11, ’6, ’1, 4, 9, 14, 19, 24, . . .}
contain elements that are related to each other and no element in one set is
related to an element in another set. In the second example the sets {sn = x : x
is n years old} for n = 0, 1, 2, . . . also divide the set of people into sets that are
Introduction
10


related to each other. Also no person can belong to two sets. (See the de¬nition
of partition below.)

Notation 1.1 Let R be an equivalence relation on a set A and a ∈ A. Then
[a]R = {x : xRa}. If the relation is understood, then [a]R is simply denoted by
[a]. Let [A]R = {[a]R : a ∈ A}.

De¬nition 1.18 Let A and I be nonempty sets and A = {Ai : i ∈ I } be a
set of nonempty subsets of A. The set A is called a partition of A if both of
the following are satis¬ed:

(a) Ai © A j = … for all i = j.
(b) A = Ai ; that is, a ∈ A if and only if a ∈ Ai for some i ∈ I .
i∈I

Theorem 1.3 A nonempty set of subsets A of a set A is a partition of A if
and only if A = [A]R for some equivalence relation R.

Proof Let A = {Ai : i ∈ I } be a partition of A. De¬ne a relation R on A by
aRb if and only if a and b are in the same subset Ai for some i. Certainly for
all a in A, aRa and R is re¬‚exive. If a and b are in the same subset Ai , then b
and a are in the subset Ai and R is symmetric. Since the sets Ai © A j = … for
i = j, if a and b are in the same subset and b and c are in the same subset, then
a and c are in the same subset. Hence R is transitive and R is an equivalence
relation.
Conversely, assume that R is an equivalence relation. We need to show that
[A]R = {[a] : a ∈ A} is a partition of A. Certainly, for all a, [a] is nonempty
since a ∈ [a]. Obviously, A is the union of the [a], such that a ∈ A. Assume
that [a] © [b] is nonempty and let x ∈ [a] © [b]. Then xRa and xRb, and by
symmetry, aRx. But since aRx and xRb, by transitivity, aRb. Therefore,
a ∈ [b]. If y ∈ [a], then yRa and since aRb, by transitivity, yRb. There-
fore, [a] ⊆ [b]. Similarly, [b] ⊆ [a] so that [a] = [b], and we have a partition
of A.

[A]R is called the set of equivalence classes of A given by
De¬nition 1.19
the relation R.

If the symmetric property is changed to antisymmetric property, we have the
following:

De¬nition 1.20 A relation R on A is a partial ordering if it is re¬‚exive,
antisymmetric, and transitive. If R is a partial ordering on A, then (A, R) is
called a partially ordered set or a poset.
1.2 Relations 11


Example 1.20 Let A be collection of subsets of a set S. De¬ne the relation
¤ by U ¤ V if U ⊆ V . It is easily seen that (A, ⊆ ) is a partially ordered set.

Example 1.21 Let R be the set of real numbers. De¬ne the relation ¤ by
r ¤ s if r is less than or equal to s using the usual ordering on R.

De¬nition 1.21 Let (A, ¤) be a partially ordered set. If a, b ∈ A and either
a ¤ b or b ¤ a then a and b are said to be comparable. If for every a, b ∈ A,
a and b are comparable then (A, ¤) is called a chain or a total ordering.

De¬nition 1.22 For a subset B of a poset A, an element a of A is an upper
bound of B if b ¤ a (or a ≥ b) for all b in B. The element a is called a least
upper bound ( lub) of B if (i) a is an upper bound of B and (ii) if any other
element a of A is an upper bound of B, then a ¤ a . The least upper bound for
the entire poset A (if it exists) is called the greatest element of A. For a subset
B of a poset A, an element a of A is a lower bound of B if a ¤ b (or b ≥ a)
for all b in B. The element a is called a greatest lower bound (glb) of B if (i)
a is a lower bound of B and (ii) if any other element a of A is a lower bound
of B, then a ≥ a . The greatest lower bound for the entire poset A (if it exists)
is called the least element of A.

Let C = {a, b, c} and X be the power set of C.
Example 1.22

X = P(C) = {…, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}}.

De¬ne the relation ¤ on X by T ¤ V if T ⊆ V . By de¬nition, {a, b} is the
greatest lower bound of {…, {a}, {b}} and also of {…, {a}, {b}, {a, b}}. The set
{a, b, c} is the least upper bound of X . The element … is the greatest lower
bound for all three sets.

De¬nition 1.23 A poset A for which every pair of elements of A have a least
upper bound in A is called an upper semilattice and is denoted by (A, ∨) or
(A, +).

If every two elements of a poset A have a greatest lower bound in A, then
the following binary relation can be de¬ned on the set. If a and b belong to A,
let a § b = glb{a, b}.

De¬nition 1.24 A poset A for which every pair of elements of A have a greatest
lower bound in A is called a lower semilattice and is denoted by (A, § ) or
(A, ·).

Example 1.22 is an example of a poset which is both an upper semilattice
and a lower semilattice.
Introduction
12


Exercises
(1) What is wrong with the following proof?
If a relation R on a set A is symmetric and transitive, then it is re¬‚exive.
Proof Since R is symmetric, if a Rb then b Ra. Since A is transitive,
if a Rb and b Ra then a Ra. Therefore a Ra and R is re¬‚exive.
(2) Give an example of a relation R on a set A that is re¬‚exive and symmetric,
but not transitive.
(3) Give an example of a relation R on a set A that is re¬‚exive and transitive,
but not symmetric.
(4) Let σ and „ be relations of a set A. Show that σ ⊆ „ if and only if each
equivalence class in the set of equivalence classes given by „ is a union of
equivalence classes given by σ .
(5) A relation R of A is a partial order if it is re¬‚exive, antisymmetric, and
transitive. It is a total order or chain if for any two elements a, b ∈ A,
either a Rb or b Ra. Give an example of a partial order that is not a total
order.
(6) Prove that the intersection of two partial orders on a set A is a partial order.
(7) Prove that the intersection of two equivalence relations on a set A is an
equivalence relation.
(8) Given a set A, what is the intersection of all equivalence relations on A?
(9) Let A be the set of ordered pairs of positive integers. De¬ne the relation R
on A by (a, b)R(c, d) if ad = bc. Is R an equivalence relation? If so what
are the equivalence classes?




1.3 Functions
De¬nition 1.25 A relation f on A — B is a function from A to B, denoted
by f : A ’ B, if for every a ∈ A there is one and only one b ∈ B so that
(a, b) ∈ f . If f : A ’ B is a function and (a, b) ∈ f , we say that b = f (a).
The set A is called the domain of the function f and B is called the codomain.
If E ⊆ A, then f (E) = {b : f (a) = b for some a in E} is called the image of
E. The image of A itself is called the range of f . If F ⊆ B, then f ’1 (F) = {a :
f (a) ∈ F} is called the preimage of F. A function f : A ’ B is also called a
mapping and we speak of the domain A being mapped into B by the mapping
f . If (a, b) ∈ f so that b = f (a), then we say that the element a is mapped to
the element b.

The proof of the following theorem is left to the reader.
1.3 Functions 13


Theorem 1.4 Let f : A ’ B.

f (A1 ∪ A2 ) = f (A1 ) ∪ f (A2 ) for A1 , A2 ⊆ A.
(a)
f ’1 (B1 ∪ B2 ) = f ’1 (B1 ) ∪ f ’1 (B2 ) for B1 , B2 ⊆ B.
(b)
f (A1 © A2 ) ⊆ f (A1 ) © f (A2 ) for A1 , A2 ⊆ A.
(c)
f ’1 (B1 © B2 ) = f ’1 (B1 ) © f ’1 (B2 ) for B1 , B2 ⊆ B.
(d)
f ’1 (B1 ) = ( f ’1 (B1 )) for B1 ⊆ B.
(e)

De¬nition 1.26 If f : A ’ B, and the image of f is B, then f is onto. It is
also called a surjection or an epimorphism. Thus for element b ∈ B, there is
an element a ∈ A so that b = f (a).

De¬nition 1.27 If f : A ’ B, and f (a) = f (a ) ’ a = a for all a, a ∈ A
then f is one-to-one. It is also called a monomorphism or injection.

De¬nition 1.28 If f : A ’ B is one-to-one and onto, then f is called a
one-to-one correspondence or bijection. If A is ¬nite, then f is also called a
permutation.

Notation 1.2 If f is a permutation on the set {1, 2, 3, . . . , n}, then it can be
represented in the form

... n
1 2
.
. . . f (n)
f (1) f (2)

Thus if f (a) = b, f (b) = d, f (c) = a, and f (d) = c, we may denote this by
abcd 1234 1234
. If f = and g = , to ¬nd
bdac 3412 2341
the composition f —¦ g note that since g(1) = 2 appears under 1 in the permuta-
tion for g, and f (2) = 4, appears under 2 in f , we may ¬nd ( f —¦ g)(1) by going
from 1 down to 2 in g and then going from 2 down to 4 in the permutation f , so
( f —¦ g)(1) = 4. Similarly, to ¬nd ( f —¦ g)(2), go down from 2 to 3 in g and from
1234
3 to 1 in f , so ( f —¦ g)(2) = 1. Continuing, we have f —¦ g = .
4123

Example 1.23 Let f : A ’ B, where A and B are the set of real numbers, be
de¬ned by f (x) = x 2 , then f is a function whose range is the set of nonnegative
real numbers. It is not onto since the range is not B. It is not one-to-one since
f (2) = f (’2) = 4.

Example 1.24 Let f : A ’ B, where A and B are the set of real numbers,
be de¬ned by f (x) = x 3 , then f is a function whose range is B. Hence it is
onto. It is also one-to-one since a 3 = (a )3 ’ a = a .
Introduction
14


De¬nition 1.29 Let I : A ’ A be de¬ned by I (a) = a for all a ∈ A. The
function I is called the identity function.
De¬nition 1.30 Let g : A ’ B and f : B ’ C, then ( f —¦ g)(x) = f (g(x)).
The proof of the following theorem is elementary and is left to the reader:
Theorem 1.5 Let f : A ’ A, then I —¦ f = f —¦ I = f .
Theorem 1.6 Let f : A ’ B then there exists a function f ’1 : B ’ A so
that f —¦ f ’1 = f ’1 —¦ f = I if and only if f is a bijection. The function f ’1
is also a bijection.

Proof Assume there exists a function f ’1 : B ’ A so that f —¦ f ’1 = f ’1 —¦
f = I , and f (a) = f (a ). Then f ’1 —¦ f (a) = f ’1 —¦ f (a ), so I (a) = I (a )
and a = a . Therefore f is one-to-one. Let b ∈ B and a = f ’1 (b). Then f (a) =
f ( f ’1 (b)) = b, f is onto.
Assume f : A ’ B is a bijection. De¬ne the relation f ’1 on B — A by
f ’1 (b) = a if f (a) = b. Let b ∈ B and choose a so that f (a) = b. This is
possible since f is onto. Therefore f ’1 (b) = a and f ’1 has domain B. If
f ’1 (b) = a and f ’1 (b) = a , then f (a) = b and f (a ) = b. But since f is
one-to-one, a = a . Therefore f ’1 is well de¬ned and hence f ’1 is a function.
By de¬nition f —¦ f ’1 = f ’1 —¦ f = I .
By symmetry, f ’1 is a bijection.

The proof of the following theorem is left to the reader:
Theorem 1.7 Let g : A ’ B and f : B ’ C; then:
If g and f are onto B and C, respectively, then f —¦ g is onto C.
(a)
If g and f are both one-to-one, then f —¦ g is one-to-one.
(b)
If g and f are both one-to-one and onto, then f —¦ g is one-to-one and onto.
(c)
If g and f have inverses, then ( f —¦ g)’1 = g ’1 —¦ f ’1 .
(d)
Theorem 1.8 Let f : A ’ B be a function. The relation R de¬ned by a Ra
if f (a) = f (a ) is an equivalence relation.

Proof Let a, a , a ∈ A. Certainly f (a) = f (a) so R is re¬‚exive. If f (a) =
f (a ), then f (a ) = f (a), so R is symmetric. If f (a) = f (a ) and f (a ) =
f (a ), then f (a) = f (a ) so R is transitive. Therefore R is an equivalence
relation.

De¬nition 1.31 Let R be an equivalence relation on A, and φR : A ’ [A]R
be a function de¬ned by φR (a) = [a]. The function φR is called the canonical
function from A to [A]R .
1.3 Functions 15


Theorem 1.9 Let f : A ’ B be a function and R be the relation aRa iff
f (a) = f (a ), then there exists a function g : [A]R ’ B de¬ned by g(aR ) =
f (a). Hence g —¦ φR = f .

f
B
A
fR
g

[A]R


Proof Assume g([a]) = b and g([a]) = b , then f (a) = b and f (a ) = b ,
where [a] = [a ]. But then aRa and f (a) = f (a ). Therefore b = b and g is
a function.

Theorem 1.10 Let f : [A]R ’ B be a function and S be an equivalence
relation such that S ⊆ R and aSa ’ aRa , then there exist functions g :
[A]S ’ B and i : [A]S ’ [A]R such that f —¦ i = g.

f
B
[A]
R
i g

[A]
S



Proof Let i : [A]S ’ [A]R be de¬ned by i([a]S ) = [a]R and g : [A]S ’ B
by g([a]S ) = f ([aR ]). The function i is trivially well de¬ned. The proof that g
is a function is similar to the proof of the previous theorem.


Exercises
(1) Prove Theorem 1.4. Let f : A ’ B.
(a) f (A1 ∪ A2 ) = f (A1 ) ∪ f (A2 ) for A1 , A2 ⊆ A.
(b) f ’1 (B1 ∪ B2 ) = f ’1 (B1 ) ∪ f ’1 (B2 ) for B1 , B2 ⊆ B.
(c) f (A1 © A2 ) ⊆ f (A1 ) © f (A2 ) for A1 , A2 ⊆ A.
(d) f ’1 (B1 © B2 ) = f ’1 (B1 ) © f ’1 (B2 ) for B1 , B2 ⊆ B.
(e) f ’1 (B1 ) = ( f ’1 (B1 )) for B1 ⊆ B.
(2) Prove Theorem 1.7. Let g : A ’ B and f : B ’ C; then:
(a) If g and f are onto B and C, respectively, then f —¦ g is onto C.
(b) If g and f are both one-to-one, then f —¦ g is one-to-one.
(c) If g and f are both one-to-one and onto, then f —¦ g is one-to-one and
onto.
(d) If g and f have inverses, then ( f —¦ g)’1 = g ’1 —¦ f ’1 .
Introduction
16


(3) Give an example of a function f and sets A1 , A2 ⊆ A such that f (A1 ©
A2 ) = f (A1 ) © f (A2 ).
(4) Prove that if f —¦ g is one-to-one then g is one-to-one.
(5) Prove that if f —¦ g is onto, then f is onto.


1.4 Semigroups
: S — S ’ S we shall use the notation a a for
In the following function
((a, a )).
De¬nition 1.32 A semigroup is a nonempty set S together with a function
from S — S ’ S such that
a ) = (a a ) a .
a (a
The function or operation with this property is called associative. The semi-
group is denoted by (S, ) or simply S if the operation is understood. If S
contains an identity element 1 such that 1 a = a 1 = a for all a ∈ A, then S
is called a monoid. If S contains an element 0 such that 0 a = a 0 = 0 for
all a ∈ A, then S is called a semigroup with zero. A semigroup is commutative
if a a = a a for all a, a ∈ A.
Example 1.25 Examples of semigroups include
(1) The set of integers [positive integers, real numbers, positive real numbers,
rational numbers, positive rational numbers] together with either of the
operations addition or multiplication is a semigroup.
(2) The set of functions { f | f : A ’ A} for a given set A, together with the
operation —¦ where ( f —¦ g)(x) = f (g(x)) is a semigroup.
(3) The set of n — n matrices with either of the operations addition or multi-
plication is a semigroup.
Example 1.26 The set of nonnegative integers together with the operation
addition is a monoid. All of the above examples except for the positive real
numbers, positive integers, and positive rational numbers with the operation
addition form a monoid.
Every semigroup S can be changed to a monoid by simply adding an element
1 and de¬ning 1 a = a 1 = a for all a ∈ S. If S was already a monoid, it
remains a monoid but with a different identity element. Normally one adds an
identity element to a semigroup only if it is not already a monoid. Similarly
every semigroup S can be changed to a semigroup with zero by simply adding
an element 0 and de¬ne 0 a = a 0 = 0 for all a ∈ S. Note that if we let Sm
1.4 Semigroups 17


be the set of all integers greater than or equal to m, then (Sm , +) is a semigroup.
If we include 0, then we have a monoid. Also since (Sm , ·) is a semigroup, if
we include 1, then we have a monoid.
Notation 1.3 Let S be a semigroup. The monoid S 1 = S if S is already a
monoid, and S 1 = S ∪ {1} otherwise. The semigroup S 0 = S if S is already a
semigroup with zero and S 0 = S ∪ {0} otherwise.
De¬nition 1.33 Let (S, ) be a semigroup and H be a nonempty subset of S. If
for all h, h ∈ H , h h ∈ H , then (H, ) is a subsemigroup of (S, ). If (S, )
is a monoid and (H, ) is a subsemigroup of (S, ) containing the identity of
the monoid, then (H, ) is a submonoid of (S, ).
Therefore the set of positive integers with the operation multiplication is a
submonoid of the integers with the operation multiplication. The semigroup
(Sm , +) is a subsemigroup of (Sn , +) for m ¤ n.
Theorem 1.11 Let (S, ) be a semigroup and {Hi : i ∈ I } be subsemigroups
of S. If the intersection Hi is nonempty, then it is a subsemigroup of S.
i∈I

Let h, h ∈ Hi . Then h, h ∈ Hi for each i ∈ I and h h ∈ Hi for
Proof
i∈I
each i. Therefore h h ∈ Hi , and Hi is a subsemigroup of S.
i∈I i∈I

Corollary 1.1 Let (S, ) be a monoid and {Hi : i ∈ I } be submonoids of I .
The intersection Hi is a submonoid.
i∈I

Theorem 1.12 Let (S, ) be a semigroup and W be a nonempty subset of S.
There exists a smallest subsemigroup of S containing W .
Proof Let H be the intersection of all subsemigroups of S containing W .
By the previous theorem H is a subsemigroup and is contained in all other
subsemigroups of S containing W .
De¬nition 1.34 The smallest subsemigroup of S containing the nonempty set
W is the semigroup generated by W . It is denoted by W .
The proof of the following theorem is left to the reader.
Theorem 1.13 Let (S, ) be a semigroup and W be a nonempty subset of S.
The set of all ¬nite products of elements of W together with the elements of W
is the semigroup generated by W .
De¬nition 1.35 Let (M, ) be a monoid and W be a nonempty subset of M.
The semigroup generated by W , together with the identity of M is called the
monoid generated by W . It is denoted by W — .
Introduction
18


De¬nition 1.36 A commutative semigroup (S, —) is a semilattice if a — a = a
for all a ∈ S. An element a of a semigroup is called an idempotent element if
a — a = a. A semilattice is therefore a commutative semigroup in which every
element is an idempotent. If (S, —) is a semilattice and S ⊆ S then S is a
subsemilattice of S if — is a binary operation on S. Equivalently, (S, —) is a
subsemilattice of (S, —) if S ⊆ S and for every a, b ∈ S, a — b ∈ S.

Example 1.27 The semigroup consisting of all subsets of a ¬xed set T
together with the operation © is a semilattice.

Obviously lower semilattices and upper semilattices are semilattices. Con-
versely given a semilattice (S, —), a partial ordering on S can be de¬ned by
s ¤ t if s — t = t.

De¬nition 1.37 If (S, —) is both a lower semilattice and an upper semilattice
then it is called a lattice. If for any lattice (S, —) and any subset T of S, both
the greatest lower bound and the least upper bound exist, then (S, —) is called
a complete lattice.

De¬nition 1.38 A group G is a monoid such that for every g ∈ G, there exists
g ’1 ∈ G such that gg ’1 = g ’1 g = 1 where 1 is the identity of the monoid.

If a semigroup (S, ) is in¬nite, then it is possible that the semigroup
generated by {a} is in¬nite. It consists of the elements {a, a 2 , a 3 , . . .} where
a k+1 = a k a. For example, if Z is the semigroup of integers under addition,
then the semigroup generated by {2} is {2, 4, 6, 8, . . .}. If a semigroup (S, ) is
¬nite, however, for some k and m, a k = a k+m . Pick the smallest k and m, then
a k , a k+1 , a k+2 , . . . , a m’1 form a semigroup. If each element is multiplied by a k
we again get a k , a k+1 , a k+2 , . . . , a m’1 so there is some a i so that a k a i = a k .
Therefore a i a k+ j = a k+ j for all 0 ¤ j ¤ m ’ 1 and a i is the identity of the
semigroup.Therefore the semigroup is a monoid. Also for each a j there exist
a n such that a j a n = a n a j = a i . This element is called the inverse of a j .
Hence this set forms a group.

De¬nition 1.39 A function f from the semigroup (S, ) to the semigroup (T, •)
is called a semigroup homomorphism if f (s s ) = f (s) • f (s ) for all s, s ∈
S. If the semigroup f is one-to-one and onto, then f is called a semigroup
isomorphism. A function f from the monoid (S, ) to the monoid (T, •) is
called a monoid homomorphism if f (s s ) = f (s) • f (s ) for all s, s ∈ S
and f maps the identity of S to the identity of T . If a monoid homomorphism
f is one-to-one and onto, then f is called a monoid isomorphism.
1.4 Semigroups 19


Normally when a function is a homomorphism from a monoid to a monoid,
we shall assume that it is a monoid homomorphism and simply call it a
homomorphism.
Example 1.28 Let f : (Z , +) ’ (Z , +) be de¬ned by f (a) = 2a, then f is
a semigroup homomorphism. It is also a monoid homomorphism.
Example 1.29 Let 2Z be the set of even integers and f : (Z , +) ’ (2Z , +)
be de¬ned by f (a) = 2a, then f is a monoid homomorphism. It is also a monoid
isomorphism.
Example 1.30 Let S be the semigroup of n — n matrices with the operation
multiplication, R be the semigroup of real numbers with the operation multipli-
cation, and det(A) be the determinant of a matrix A. Then det : (S, ·) ’ (R, ·)
is a homomorphism.
Example 1.31 Let R+ denote the semigroup of positive real numbers with
the operation multiplication and ln be the natural logarithm, then ln : (R+ , ·) ’
(R, +) is a homomorphism.
The following theorem is left to the reader:
Theorem 1.14 Let f : S ’ T be a homomorphism, then
(a) If S is a subsemigroup [submonoid] of S, then f (S ) is a subsemigroup
[submonoid] of T .
(b) If T is a subsemigroup [submonoid] of T , then f ’1 (T ) is a subsemigroup
[submonoid] of S.
(c) If f : S ’ T is an isomorphism, then f ’1 : T ’ S is an isomorphism.
De¬nition 1.40 A nonempty subset T of a semigroup S is a left ideal of S if
s ∈ S and t ∈ T implies ts ∈ T . A nonempty subset T of a semigroup S is a
right ideal of S if s ∈ S and t ∈ T implies st ∈ T . A subset T of a semigroup
S is an ideal of S if it is both a left ideal of S and a right ideal of S.
Obviously an ideal of S is a subsemigroup of S.
Example 1.32 Let S be the semigroup of 2 — 2 matrices with multiplication
a0
as the operation and the integers as elements. Then matrices of the form
b0
ab
form a left ideal and matrices of the form form a right ideal.
00
Example 1.33 The semigroup of even integers form an ideal of (Z , ·).
De¬nition 1.41 An equivalence relation R on a semigroup S is a congruence
if for all a, b, c, d ∈ S, aRb and cRd imply acRbd.
Introduction
20


De¬nition 1.42 Let R be a congruence on a semigroup S. Let aR be the
congruence class containing a. The set S/R of all the congruence classes with
the multiplication aR · bR = (a b)R is called the quotient semigroup relative
to the congruence R.
Example 1.34 Let R, the set of real numbers, be a semigroup with the oper-
ation addition [multiplication] and de¬ne aRb if a ’ b is a multiple of 5.
Then [0], [1], [2], [3], and [4] form a semigroup with the operation addition
[multiplication].
The proof of the following theorem is left to the reader.
Theorem 1.15 Let R be a congruence on a semigroup S. Then S/R is a
semigroup with the operation de¬ned in the previous de¬nition and φR : S ’
S/R de¬ned by φR (s) = sR is a homomorphism.
Theorem 1.16 Let f : A ’ B be a homomorphism and R be the congru-
ence aRa iff f (a) = f (a ), then there exists a homomorphism g : A/R ’ B
de¬ned by g(aR ) = f (a). Hence g —¦ φR = f .

f
B
[A]
fR
g

A/R


Proof We showed in Theorem 1.9 that g is a function.
g(aR · aR ) = f (a · a )
= f (a) · f (a )
= g(aR ) · g(aR ).


Theorem 1.17 Let f : A/R ’ B be a function and S ⊆ R, so if aSa
implies aRa , then there exist functions g : A/S ’ B and i : A/S ’ A/R
such that f —¦ i = g.

f
B
A/R
g
i
A/S


Proof Let i : A/S ’ A/R be de¬ned by i(aS ) = aR and g : A/S ’ B by
g(aS ) = f (aR ). The function i is trivially well de¬ned and a homomorphism.
1.4 Semigroups 21


The proof that g is a function is similar to the proof of Theorem 1.9. (See
Theorem 1.10).
g(aS · aS ) = g(aaS )
= f (aaR )
= f (aR aR )
= f (aR ) f (aR )
= g(aS )g(aS ).


We already know that the set of all functions from a set A to itself form a
semigroup since for a ∈ A, and functions f , g, and h from A to itself, (( f —¦
(g —¦ h))(a) = (( f —¦ g) —¦ h)(a) = f (g(h(a). Also since f , g, and h are relations
we have already proven that ( f —¦ (g —¦ h) = ( f —¦ g) —¦ h.
Conversely, given a semigroup S, and s ∈ S we can de¬ne a function φs :
S ’ S by φs (t) = st for all t ∈ S. Let T S = {φs : S ’ S for s ∈ S}. For all
s, t, and u in S,
φst (u) = st(u)
= φs (tu) = φs φt (u)
= (φs —¦ φt )(u)
and φst = (φs —¦ φt ). Let „ : S ’ T S be de¬ned by „ (s) = φs . The function „
is a homomorphism since

„ (st) = φst = φs —¦ φt = „ (s) · „ (t).

Theorem 1.18 Every semigroup is isomorphic to a semigroup of functions
from a set to itself with operation composition. If S is a monoid, then S is
isomorphic to a monoid of functions from S to itself.

Proof Given a semigroup S, and s ∈ S de¬ne φs : S 1 ’ S 1 by φs (t) = st
1 1

for all t ∈ S 1 and let T S1 = {φs : S 1 ’ S 1 for s ∈ S}. Let „ 1 : S ’ T S1 be
1

de¬ned by „ 1 (s) = φs . Using the same argument as above, we see that „ 1 is
1

a homomorphism. But if φs = φt1 , since φs (1) = s1 = s and φt1 (1) = t1 = t
1 1

then s = t and „ 1 is an isomorphism. The second part of the theorem follows
immediately.


Exercises
(1) Prove Theorem 1.13. Let (S, ) be a semigroup and W be a nonempty
subset of S. The set of all ¬nite products of elements of W together with
the elements of W is the subsemigroup generated by W .
Introduction
22


(2) Prove Theorem 1.14. Let f : S ’ T be a homomorphism, then
(a) If S is a subsemigroup [submonoid] of S, then f (S ) is a subsemigroup
[submonoid] of T .
(b) If T is a subsemigroup [submonoid] of T , then f ’1 (T ) is a subsemi-
group [submonoid] of S.
(c) If f : S ’ T is an isomorphism, then f ’1 : T ’ S is an isomor-
phism.
(3) Prove Theorem 1.15. Let R be a congruence on a semigroup S. Then
S/R is a semigroup with the operation de¬ned by aR · bR = (a b)R and
φR : S ’ S/R is a homomorphism.
(4) Prove that a ¬nite semigroup S contains a subgroup.
(5) Give an example of a group which contains a subsemigroup that is not a
monoid.
(6) Prove that the identity of a monoid is unique.
(7) Prove that if a semigroup contains a 0, then it is unique.
(8) Prove that if G is a ¬nite group and H is a subgroup of G, then |H | = |g H |
for every g ∈ G.
(9) Prove that if G is a ¬nite group and H is a subgroup of G, then H = g H
if and only if g ∈ H.
(10) Prove that if G is a ¬nite group and H is a subgroup of G, then |H | divides
|G|.
(11) An idempotent of a semigroup S is an element a such that a · a = a. Prove
that if f : S ’ T is a homomorphism, then if a is an idempotent, f (a)
is an idempotent.
(12) An element a of a semigroup S is a left identity if as = s for all s ∈ S.
An element a of a semigroup S is a right identity if sa = s for all s ∈ S.
Give an example of a semigroup having more that one left identity.
(13) Let f : S ’ T be a homomorphism. Prove that if T contains 0, then
f ’1 (0) is an ideal.
(14) Using the properties in Theorem 1.1, prove that if S = P(C) for some
nonempty set C, then (S, ) is a monoid, where denotes the symmetric
difference. What is the identity? Is (S, ) a group?
(15) Let S = P(C) for some nonempty set C, is (S, ∪) a monoid? Is (S, ©) a
monoid? Are they groups?
(16) De¬ne the multiplication of permutations of a set to be composition as
shown in the previous section. Prove that the set of permutations of a set
with this multiplication form a group.
2
Languages and codes




2.1 Regular languages
De¬nition 2.1 An alphabet, denoted by , is a set of symbols. A string or
word is a sequence a1 a2 a3 a4 . . . an where ai ∈ .
Thus if = {a, b}, then aab, a, baba, bbbbb, and baaaaa would all be
strings of symbols of . In addition we include an empty string denoted by »
which has no symbols in it.
De¬nition 2.2 Let — denote the set of all strings of including the empty
string. De¬ne the binary operation —¦ called concatenation on — as follows:
If a1 a2 a3 a4 . . . an and b1 b2 b3 b4 . . . bm ∈ — then
a1 a2 a3 a4 . . . an —¦ b1 b2 b3 b4 . . . bm = a1 a2 a3 a4 . . . an b1 b2 b3 b4 . . . bm .

then S —¦ T = {s —¦ t : s ∈ S, t ∈ T }. The set S —¦ T
If S and T are subsets of
is often denoted as ST .
Thus if = {a, b}, then aabba —¦ babaa = aabbababaa. In particular, if ω
is a string in — then » —¦ ω = ω —¦ » = ω, so that a string followed or preceded
by the empty string simply gives the original string. Notice that in general it is
not true that w —¦ v = v —¦ w.
The following is a speci¬c case of the submonoid generated by a subset of
a monoid described in Chapter 1.
De¬nition 2.3 Let B be a subset of — then B — is the set of all strings or
words formed by concatenating words from B together with the empty string, i.e.
B — = {w1 w2 . . . wn : wi ∈ B} ∪ {»}. If … denotes the empty set then …— = {»}.
The symbol — is called the Kleene star and is named after the mathematician
and logician Stephen Cole Kleene.
Note that — is consistent with this de¬nition.

23
Languages and codes
24


Example 2.1 {a}— = {», a, aa, aaa, . . .}.

{a}{ab}— {c} = {ac, aabc, aababc, . . .}.
Example 2.2

Let A+ be the set consisting of all ¬nite products of elements of a nonempty
set A together with the operation of concatenation. The set A+ = A , and
hence is a semigroup as shown in Theorem 1.13. From Theorem 1.13 and the
de¬nition of A— we know that if A is a nonempty subset of then the set

(A , —¦) is a monoid where » is the identity. It is the submonoid generated
by A. If A does not contain the empty word, then (A— , —¦) differs from (A+ , —¦)
since it contains the empty word. Thus if A = {a}, then A+ = {a, a 2 , a 3 , . . .}
and A— = {», a, a 2 , a 3 , . . .}. Note that A+ = a A— .

De¬nition 2.4 Let denote the set of all strings of including the empty

is called a language.
string. A subset L of

If is the set of letters in the English alphabet, then L could be the set of
words in the English language. If is the set of letters in the Greek alphabet,
then L could be the set of words in the Greek language. If is the set of symbols
used in a computer language, then L could be the set of words in that language.
Since every subset of — is a language, many will be dif¬cult or impossible to
describe. In particular a language is not necessarily closed under the operation
of concatenation.
If is the set {a, b, c} then the following are languages:
= {a, aab, aaabb, aaaabbb . . .},
L1
= {w : w ∈ — and contains exactly one a and one b},
L2
= {w : w ∈ — and contains exactly two bs},
L3
= {w : w ∈ — and contains at least two bs},
L4
= {w : w ∈ — and contains the same number of as, bs, and cs},
L5
= {w : w = a n bn for n ≥ 1},
L6
= {w : w = a n bn cn for n ≥ 1},
L7
= {w : w ∈ — and contains no cs}.
L8
De¬nition 2.5 Let be an alphabet. The class of regular expressions R over
is de¬ned by the following rules using and the symbols …, »,— , ∨, (,and).
The symbol » is used to denote the symbol …— .

(i) The symbol … is a regular expression and for every a ∈ , the symbol a is
a regular expression.

(ii) If w1 and w2 are regular expressions, then w1 w2 , w1 ∨ w2 , w1 , and (w1 )
are regular expressions.
(iii) There are no regular expressions which are not generated by (i) and (ii).
2.1 Regular languages 25


Each expression corresponds to a set with the following correspondence £
de¬ned by
= …,
£(…)
= {a} for all a ∈ ,
£(a)
= {»},
£(»)
£(w1 ∨ w2 ) = £(w1 ) ∪ £(w2 ) for expressions w1 , w2 ,
£(w1 w2 ) = £(w1 ) —¦ £(w2 ),

= £(w1 )— ,
£(w1 )
so that
£(aa— ) = {a} —¦ {a}— = {a, aa, aaa, aaaa, aaaa, . . .},
£(a(b ∨ c)d) = {a} —¦ {{b} ∪ {c}} —¦ {d} = {abd, acd},
£((a ∨ b)— ) = {a ∪ b}— = {», a, b, ab, ba, abb, aba, . . .}
= all strings consisting of
0 or more as and bs,
— —
= {a} —¦ {b} —¦ {c} = {ac, abc, abbc, abbbc, . . .},
£(ab c)
— — — — — —
£(a ∨ b ∨ c ) = {a} ∪ {b} ∪ {c} = {», a, b, c, . . . , a k , bk , ck . . .},
= £(…— ) = {»},
£(»)
£((a ∨ b)c)) = ({a} ∪ {b}) —¦ {c} = {ac, bc}.
The image of a regular expression is a regular language. Regular languages
may be de¬ned as follows:
De¬nition 2.6 The class R of a regular languages over has the following
properties:
(i) The empty set, … ∈ R, and if a ∈ , then {a} ∈ R.

(ii) If s1 and s2 ∈ R, then s1 ∪ s2 , s1 —¦ s2 , s1 ∈ R.
(iii) Only sets formed using (i) and (ii) belong to R.
Although it will not be shown until later, the intersection of regular sets is a
regular set and the complement of a regular set is a regular set.
The previous de¬nitions of regular languages and regular expressions are
examples of recursive de¬nitions. In a recursive de¬nition there are three
steps. (1) Certain objects are de¬ned to be in the set. (2) Rules are listed for
producing new objects in the set from other objects already in the set. (3) There
are no other elements in the set. Mathematical induction is a special case of a
recursive de¬nition. We shall see that the set {ab, a 2 b2 , . . . , a n bn , . . .} is not
a regular set. However, we cannot assume this is the case because we cannot
immediately describe the set using the de¬nition. In general it is not always
easy to show that a set is not regular. Later, we shall show how to determine
that many sets are not regular.
Languages and codes
26


Example 2.3 Examples of regular expressions include (a ∨ b)— , (a— ∨ b — ),
a— (c ∨ d) a (b ∨ a ∨ c)— , and ». Examples of regular sets include {a, b, c},
{a}— , {ab}— , {c}{b}— , {a} ∨ {b} ∨ {cd}, and ({a} ∨ {b})— ∨ {c— d} ∨ {»}.
As mentioned previously, not all classes of languages are so easily de¬ned.
In the following chapters we shall de¬ne machines that generate languages
and machines that accept languages. A machine accepts a language if it can
determine whether a string is in the language. Many languages are de¬ned by
the fact that they can be generated or accepted by a particular type of machine.
If T — = S, T is not usually uniquely de¬ned. If T = {a, b, c, d}, and

T = {a, b, c, d, ab, cd, bc}, then T — = T but, while every string in T — can
be expressed uniquely as the concatenation of elements of T , this is not true of
elements of T since the expression abcd can be expressed as (a)(b)(c)(d), and
also as (a)(b)(cd), (a)(bc)(d), (ab)(cd), etc.
De¬nition 2.7 A code is a subset of — . If C is a subset of — and every string
in S can be expressed as the concatenation of elements of C, then we say that
C is a code for S. A code C is uniquely decipherable if every string in S can
be uniquely expressed as the concatenation of elements of C.
Therefore {ba, ab, ca}, {ade, ddbee, d f c, dgd}, and {ae, b, c, de} are
uniquely decipherable codes while {a, ab, bc, c}, {ab, abc, cde, de}, and
{a, bc, ab, c} are not uniquely decipherable codes.
Note that in many texts, a subset of — is de¬ned to be a code only if it is
uniquely decipherable.
De¬nition 2.8 Let be an alphabet. A nonempty code C ⊆ — is called a
pre¬x code if for all words u, v ∈ C, if u = vw for w ∈ — , then u = v and
w = ». This means that no word in a code can be the beginning string of another
word in the code. A nonempty code C ⊆ — is called a suf¬x code if for all
words u, v ∈ C, if u = wv for w ∈ — , then u = v and w = ». This means
that no word in a code can be the ¬nal string of another word in the code. A
nonempty code C ⊆ — is called a bipre¬x code if it is both a pre¬x and a suf¬x
code. A nonempty code C ⊆ — is called an in¬x code if no word in the code
can be a substring of another word in the code so that if u and wuv are words
in the code for w, v ∈ — , then w = v = ». A code is called a block code if
each string in the code has equal length.
The set {a, ab, abc} is a uniquely decipherable code but it is not a pre¬x
code since a is the initial string of both ab and abc and ab is an initial string of
abc. It is however a suf¬x code. The set {a, ba, ca} is a pre¬x code, but it is not
a suf¬x code since a is the ¬nal string of both ba and ca. The set {ad, ab, ac}
is a bipre¬x code. Any code whose regular expression begins with a — is not a
2.1 Regular languages 27


suf¬x code and any code whose regular expression ends with a — is not a pre¬x
code. However, a — b is a pre¬x code and ab— is a suf¬x code.
The proofs of the following theorems are left to the reader:

Theorem 2.1 If a code is a suf¬x, pre¬x, in¬x, bipre¬x, or block code, then it
is uniquely decipherable.

A block code is a suf¬x, pre¬x, in¬x, and bipre¬x code.
Theorem 2.2

An in¬x code is a bipre¬x code.
Theorem 2.3


Exercises
(1) Given w = 10110, ¬nd ¬ve words v1 , v2 , v3 , v4 , v5 such that vi w = wvi
for 1 ¤ i ¤ 5.
(2) Find regular sets corresponding to the following expressions. If the set is
in¬nite, list ten elements in the set:
(a) a (b ∨ c ∨ d) a
(b) a— b— c
(c) (a ∨ b) (c ∨ d)
(d) (ab— ») ∨ (cd)—
(e) a (bc)— d.
(3) Find regular sets corresponding to the following expressions. If the set is
in¬nite, list ten elements in the set:
(a) bc(bc)—
(b) (a ∨ b— ∨ ») (c ∨ d— )
(c) (a ∨ bc ∨ d)—
(d) (a ∨ b)(c ∨ d) b
(e) a— (b ∨ c ∨ d)— .
(4) Find regular expressions that correspond to the following regular sets:
(a) {ab, ac, ad}
(b) {ab, ac, bb, bc}
(c) {a, ab, abb, abbb, abbbb, . . .}
(d) {ab, abab, ababab, abababab, ababababab, . . .}
(e) {ab, abb, aab, aabb}.
(5) Find regular expressions that correspond to the following regular sets:
(a) {ab, acb, adb}
(b) {ab, abb, abbb, abbbb, . . .}
(c) {ad, ae, a f, bd, be, b f, cd, ce, c f }
(d) {abcd, abcbcd, abcbcbcd, abcbcbcbcd, . . .}
(e) {abcd, abe f, cdcd, cde f }.

. 1
( 9)



>>