This book presents a synthesis of the latest developments in the
mathematical theory of data processing. It discusses the fundamental
results of the theory of finite automata and of rational languages and
examines the recent concept of variety of languages which formalises the
connections between finite automata, recognizable languages and finite
semigroups.
The first four chapters of the book are devoted to the fundamental results
of the theory of automata and are illustrated by numerous examples. The
final chapter contains the most recent results of the theory (but without
the proof). The reader does not require any previous knowledge of formal
languages or automat, although a certain familiarity with algebra is
called for.
Contents
Preface vii
Foreword ix
Introduction. Relations 1
Chapter 1. Semigroups, languages and automata 5
1 Semigroups 5
1.1 Semigroups, monoids, morphisms 5
1.2 Idempotents, zero, ideal 6
1.3 Congruences 7
1.4 Semigroups of transformations 9
1.5 Free semigroups 10
2. Languages 12
2.1 Words 12
2.2 Automata 12
2.3 Rational and recognizable languages 13
2.4 Syntactic monoids 17
2.5 Codes 18
2.6 The case of free semigroups 20
3. Explicit calculations 20
3.1 Syntactic semigroups of L = A*abaA*
over the alphabet A = {a, b} 21
3.2 The syntactic monoid of L = {a2, ab,
ba}* over the alphabet A = {a, b} 23
Problems 24
Chapter 2. Varieties 27
1 Varieties of semigroups and monoids 27
1.1 Definitions and examples 27
1.2 Equations of a variety 28
2 The variety theorem 31
3 Examples of varieties 35
Problems 42
Chapter 3. Structure of finite semigroups 45
1 Green's relations 45
2 Practical computations 52
3 The Rees semigroup and the structure of regular D-classes 61
4 Varieties defined by Green's relations 65
5 Relational morphisms and V-morphisms 67
Problems 75
Chapter 4. Piecewise-testable languages and star-free
languages 79
1 Piecewise-testable languages ; Simon's theorem 79
