Varieties of formal languages

## Presentation

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

### 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

### Chapter 2. Varieties 27

#### 1 Varieties of semigroups and monoids 27

1.1 Definitions and examples 27
1.2 Equations of a variety 28

### Chapter 5. Complementary results 99

#### 1 Operations 99

1.1 Operations on languages 99
1.2 Operations on monoids 103
1.3 Operations on varieties 107

#### 2 Concatenation hierarchies 113

2.1 Locally testable languages 113
2.2 General results on concatenation hierarchies 114
2.3 Straubing's hierarchy 114
2.4 Brzozowski's hierarchy 116
2.5 Connection between teh hierarchies of Straubing and Brzozowski 117
2.6 The group-languages hierarchy 117
2.7 Hierarchies and symbolic logic 118

#### 3 Relations with the theory of codes 120

3.1 Restriction of the operations star and plus 120
3.2 Varieties described by codes 122

#### 4 Other results and problems 122

4.1 Congruences 122
4.2 The lattice of varieties 122