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 }.