Mathematical Foundations of Automata Theory

简介

contents

A Automata and semigroups 1
I Algebraic preliminaries . . . . . . . . . . . . . . . . . . . . . . . 3
1 Subsets, relations and functions . . . . . . . . . . . . . . . . . . . . 3
1.1 Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4 Injective and surjective relations . . . . . . . . . . . . . . . 6
1.5 Relations and set operations . . . . . . . . . . . . . . . . . 8
2 Ordered sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
II Semigroups and beyond . . . . . . . . . . . . . . . . . . . . . . 13
1 Semigroups, monoids and groups . . . . . . . . . . . . . . . . . . . 13
1.1 Semigroups, monoids . . . . . . . . . . . . . . . . . . . . . 13
1.2 Special elements . . . . . . . . . . . . . . . . . . . . . . . . 14
1.3 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4 Ordered semigroups and monoids . . . . . . . . . . . . . . 16
1.5 Semirings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.1 Examples of semigroups . . . . . . . . . . . . . . . . . . . . 17
2.2 Examples of monoids . . . . . . . . . . . . . . . . . . . . . 17
2.3 Examples of groups . . . . . . . . . . . . . . . . . . . . . . 18
2.4 Examples of ordered monoids . . . . . . . . . . . . . . . . . 18
2.5 Examples of semirings . . . . . . . . . . . . . . . . . . . . . 18
3 Basic algebraic structures . . . . . . . . . . . . . . . . . . . . . . . 19
3.1 Morphisms . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Subsemigroups . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.3 Quotients and divisions . . . . . . . . . . . . . . . . . . . . 21
3.4 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.5 Ideals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.6 Simple and 0-simple semigroups . . . . . . . . . . . . . . . 24
3.7 Semigroup congruences . . . . . . . . . . . . . . . . . . . . 24
4 Transformation semigroups . . . . . . . . . . . . . . . . . . . . . . 27
4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.2 Full transformation semigroups and symmetric groups . . . 28
4.3 Product and division . . . . . . . . . . . . . . . . . . . . . 28
5 Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.1 A-generated semigroups . . . . . . . . . . . . . . . . . . . . 29
5.2 Cayley graphs . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.3 Free semigroups . . . . . . . . . . . . . . . . . . . . . . . . 30
5.4 Universal properties . . . . . . . . . . . . . . . . . . . . . . 30
5.5 Presentations and rewriting systems . . . . . . . . . . . . . 31
6 Idempotents in finite semigroups . . . . . . . . . . . . . . . . . . . 32
7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
III Languages and automata . . . . . . . . . . . . . . . . . . . . . 37
1 Words and languages . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.1 Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
1.2 Orders on words . . . . . . . . . . . . . . . . . . . . . . . . 38
1.3 Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
2 Rational languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3 Automata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.1 Finite automata and recognisable languages . . . . . . . . . 42
3.2 Deterministic automata . . . . . . . . . . . . . . . . . . . . 45
3.3 Complete, accessible, coaccessible and trimmed automata . 47
3.4 Standard automata . . . . . . . . . . . . . . . . . . . . . . 47
4 Operations on recognisable languages . . . . . . . . . . . . . . . . . 48
4.1 Boolean operations . . . . . . . . . . . . . . . . . . . . . . 48
4.2 Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.3 Star . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.4 Quotients . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.5 Inverses of morphisms . . . . . . . . . . . . . . . . . . . . . 55
4.6 Minimal automata . . . . . . . . . . . . . . . . . . . . . . . 56
5 Rational versus recognisable . . . . . . . . . . . . . . . . . . . . . . 60
5.1 Local languages . . . . . . . . . . . . . . . . . . . . . . . . 60
5.2 Glushkov’s algorithm . . . . . . . . . . . . . . . . . . . . . 62
5.3 Linear equations . . . . . . . . . . . . . . . . . . . . . . . . 65
5.4 Extended automata . . . . . . . . . . . . . . . . . . . . . . 68
5.5 Kleene’s theorem . . . . . . . . . . . . . . . . . . . . . . . . 70
6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
IV Recognisable and rational sets . . . . . . . . . . . . . . . . . . 75
1 Rational subsets of a monoid . . . . . . . . . . . . . . . . . . . . . 75
2 Recognisable subsets of a monoid . . . . . . . . . . . . . . . . . . . 77
2.1 Recognition by monoid morphisms . . . . . . . . . . . . . . 77
2.2 Operations on sets . . . . . . . . . . . . . . . . . . . . . . . 79
2.3 Recognisable sets . . . . . . . . . . . . . . . . . . . . . . . . 80
3 Connection with automata . . . . . . . . . . . . . . . . . . . . . . . 83
3.1 Transition monoid of a deterministic automaton . . . . . . 83
3.2 Transition monoid of a nondeterministic automaton . . . . 85
3.3 Monoids versus automata . . . . . . . . . . . . . . . . . . . 86
4 The syntactic monoid . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
4.2 The syntactic monoid of a language . . . . . . . . . . . . . 90
4.3 Computation of the syntactic monoid of a language . . . . 91
5 Recognition by ordered structures . . . . . . . . . . . . . . . . . . . 91
5.1 Ordered automata . . . . . . . . . . . . . . . . . . . . . . . 91
5.2 Recognition by ordered monoids . . . . . . . . . . . . . . . 92
5.3 Syntactic order . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.4 Computation of the syntactic ordered monoid . . . . . . . . 93
6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
7 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
V Green’s relations and local theory . . . . . . . . . . . . . . . . 99
1 Green’s relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
2 Inverses, weak inverses and regular elements . . . . . . . . . . . . . 107
2.1 Inverses and weak inverses . . . . . . . . . . . . . . . . . . 107
2.2 Regular elements . . . . . . . . . . . . . . . . . . . . . . . . 109
3 Rees matrix semigroups . . . . . . . . . . . . . . . . . . . . . . . . 110
4 Structure of regular D-classes . . . . . . . . . . . . . . . . . . . . . 116
4.1 Structure of the minimal ideal . . . . . . . . . . . . . . . . 117
5 Green’s relations in subsemigroups and quotients . . . . . . . . . . 117
5.1 Green’s relations in subsemigroups . . . . . . . . . . . . . . 118
5.2 Green’s relations in quotient semigroups . . . . . . . . . . . 119
6 Green’s relations and transformations . . . . . . . . . . . . . . . . . 121
7 Summary: a complete example . . . . . . . . . . . . . . . . . . . . 124
8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
9 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
B Historical results 129
VI Star-free languages . . . . . . . . . . . . . . . . . . . . . . . . . 131
1 Star-free languages . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
2 Aperiodic monoids . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
3 Sch¨utzenberger’s theorem . . . . . . . . . . . . . . . . . . . . . . . 132
4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
VII Piecewise testable languages . . . . . . . . . . . . . . . . . . . 139
1 Subword ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
2 Simple languages and shuffle ideals . . . . . . . . . . . . . . . . . . 143
3 Piecewise testable languages and Simon’s theorem . . . . . . . . . . 144
4 Some consequences of Simon’s theorem . . . . . . . . . . . . . . . . 146
5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 148
6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
VIII Locally testable languages . . . . . . . . . . . . . . . . . . . . . 151
1 Scanners . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
2 A congruence on words . . . . . . . . . . . . . . . . . . . . . . . . . 152
3 Path conditions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
4 An algebraic characterization . . . . . . . . . . . . . . . . . . . . . 154
5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
IX An excursion into logic . . . . . . . . . . . . . . . . . . . . . . . 157
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
2 The formalism of logic . . . . . . . . . . . . . . . . . . . . . . . . . 157
2.1 Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
2.2 Semantics . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
2.3 Logic on words . . . . . . . . . . . . . . . . . . . . . . . . . 163
3 Monadic second-order logic on words . . . . . . . . . . . . . . . . . 165
4 First-order logic of the linear order . . . . . . . . . . . . . . . . . . 168
4.1 First order and star-free sets . . . . . . . . . . . . . . . . . 168
4.2 Σ1 formulas and piecewise testable languages . . . . . . . . 170
5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
C The profinite world 173
X Profinite words . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
1 Topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
1.1 General topology . . . . . . . . . . . . . . . . . . . . . . . . 175
1.2 Metric spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 176
1.3 Compact spaces . . . . . . . . . . . . . . . . . . . . . . . . 177
1.4 Topological semigroups . . . . . . . . . . . . . . . . . . . . 178
2 Profinite topology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178
2.1 The profinite metric . . . . . . . . . . . . . . . . . . . . . . 178
2.2 The free profinite monoid . . . . . . . . . . . . . . . . . . . 181
2.3 Universal property of the free profinite monoid . . . . . . . 183
2.4 ω-terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184
3 Recognisable languages and clopen sets . . . . . . . . . . . . . . . . 185
4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
5 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
XI Varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
1 Varieties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189
2 Free pro-V monoids . . . . . . . . . . . . . . . . . . . . . . . . . . 190
3 Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
3.1 What is an identity? . . . . . . . . . . . . . . . . . . . . . . 193
3.2 Properties of identities . . . . . . . . . . . . . . . . . . . . 194
3.3 Reiterman’s theorem . . . . . . . . . . . . . . . . . . . . . . 194
4 Examples of varieties . . . . . . . . . . . . . . . . . . . . . . . . . . 196
4.1 Varieties of semigroups . . . . . . . . . . . . . . . . . . . . 196
4.2 Varieties of monoids . . . . . . . . . . . . . . . . . . . . . . 199
4.3 Varieties of ordered monoids . . . . . . . . . . . . . . . . . 204
4.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204
5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205
6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 207
XII Equations and languages . . . . . . . . . . . . . . . . . . . . . . 209
1 Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
2 Equational characterisation of lattices . . . . . . . . . . . . . . . . 210
3 Lattices of languages closed under quotients . . . . . . . . . . . . . 212
4 Equational descriptions of lattices of languages . . . . . . . . . . . 213
4.1 The role of the zero . . . . . . . . . . . . . . . . . . . . . . 213
4.2 Languages defined by density . . . . . . . . . . . . . . . . . 216
5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221
6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222
XIII Eilenberg’s variety theory . . . . . . . . . . . . . . . . . . . . . 223
1 Streams of languages . . . . . . . . . . . . . . . . . . . . . . . . . . 223
2 C-streams . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224
3 Varieties of languages . . . . . . . . . . . . . . . . . . . . . . . . . . 226
4 The variety theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 226
5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
6 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230
XIV Algebraic characterisations . . . . . . . . . . . . . . . . . . . . 231
1 Varieties of languages . . . . . . . . . . . . . . . . . . . . . . . . . . 231
1.1 Locally finite varieties of languages . . . . . . . . . . . . . . 231
1.2 Commutative languages . . . . . . . . . . . . . . . . . . . . 234
1.3 R-trivial and L-trivial languages . . . . . . . . . . . . . . . 236
1.4 Some examples of +-varieties . . . . . . . . . . . . . . . . . 238
1.5 Cyclic and strongly cyclic languages . . . . . . . . . . . . . 240
2 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246
3 Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
D Advanced tools 249
XV Polynomial closure . . . . . . . . . . . . . . . . . . . . . . . . . 251
1 Polynomial closure of a lattice of languages . . . . . . . . . . . . . 251
2 A case study . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256
XVI Relational morphisms . . . . . . . . . . . . . . . . . . . . . . . . 257
1 Relational morphisms . . . . . . . . . . . . . . . . . . . . . . . . . . 257
2 Injective relational morphisms . . . . . . . . . . . . . . . . . . . . . 259
3 Relational V-morphisms . . . . . . . . . . . . . . . . . . . . . . . . 260
3.1 Aperiodic relational morphisms . . . . . . . . . . . . . . . . 261
3.2 Locally trivial relational morphisms . . . . . . . . . . . . . 262
3.3 Relational Jese 6 eK-morphisms . . . . . . . . . . . . . . . 263
4 Four examples of V-morphisms . . . . . . . . . . . . . . . . . . . . 264
5 Mal’cev products . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264
6 Three examples of relational morphisms . . . . . . . . . . . . . . . 265
6.1 Concatenation product . . . . . . . . . . . . . . . . . . . . 265
6.2 Pure languages . . . . . . . . . . . . . . . . . . . . . . . . . 267
6.3 Flower automata . . . . . . . . . . . . . . . . . . . . . . . . 269
XVII Unambiguous star-free languages . . . . . . . . . . . . . . . . 271
1 Unambiguous star-free languages . . . . . . . . . . . . . . . . . . . 271
XVIIIWreath product . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
1 Semidirect product . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
2 Wreath product . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273
3 Basic decomposition results . . . . . . . . . . . . . . . . . . . . . . 275
4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280
XIX Sequential functions . . . . . . . . . . . . . . . . . . . . . . . . . 281
1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281
1.1 Pure sequential transducers . . . . . . . . . . . . . . . . . . 281
1.2 Sequential transducers . . . . . . . . . . . . . . . . . . . . . 285
2 Composition of sequential functions . . . . . . . . . . . . . . . . . . 286
3 Sequential functions and wreath product . . . . . . . . . . . . . . . 290
4 The wreath product principle and its consequences . . . . . . . . . 290
4.1 The wreath product principle . . . . . . . . . . . . . . . . . 291
5 Applications of the wreath product principle . . . . . . . . . . . . . 292
5.1 The operations T 7 → U1 ◦ T and L 7 → LaA∗ . . . . . . . . . 292
5.2 The operations T 7 → ¯2 ◦ T and L 7 → La . . . . . . . . . . . 293
5.3 The operation T 7 → U2 ◦ T and star-free expressions . . . . 295
6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296
XX Concatenation hierarchies . . . . . . . . . . . . . . . . . . . . . 297
1 Concatenation hierarchies . . . . . . . . . . . . . . . . . . . . . . . 297
2 Logical hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
Annex 306
A A transformation semigroup . . . . . . . . . . . . . . . . . . . 307
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 311
Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324