Finite Automata

by Lawson; Mark V.

• ISBN13: 9781584882558
• ISBN10: 1584882557
• Edition: 1st
• Format: Hardcover
• Copyright: 2003-09-17
• Publisher: Chapman & Hall/

Summary

Interest in finite automata theory continues to grow, not only because of its applications in computer science, but also because of more recent applications in mathematics, particularly group theory and symbolic dynamics. The subject itself lies on the boundaries of mathematics and computer science, and with a balanced approach that does justice to both aspects, this book provides a well-motivated introduction to the mathematical theory of finite automata.The first half of Finite Automata focuses on the computer science side of the theory and culminates in Kleene's Theorem, which the author proves in a variety of ways to suit both computer scientists and mathematicians. In the second half, the focus shifts to the mathematical side of the theory and constructing an algebraic approach to languages. Here the author proves two main results: Schützenberger's Theorem on star-free languages and the variety theorem of Eilenberg and Schützenberger.Accessible even to students with only a basic knowledge of discrete mathematics, this treatment develops the underlying algebra gently but rigorously, and nearly 200 exercises reinforce the concepts. Whether your students' interests lie in computer science or mathematics, the well organized and flexible presentation of Finite Automata provides a route to understanding that you can tailor to their particular tastes and abilities.

Author Biography

Mark V. Lawson is Senior Lecturer in Mathematics at the University of Wales, Bangor.

Table of Contents

Preface	p. ix
Introduction to finite automata	p. 1
Alphabets and strings	p. 1
Languages	p. 5
Language operations	p. 7
Finite automata: motivation	p. 11
Finite automata and their languages	p. 14
Summary of Chapter 1	p. 21
Remarks on Chapter 1	p. 22
Recognisable languages	p. 27
Designing automata	p. 27
Incomplete automata	p. 29
Automata that count	p. 33
Automata that locate patterns	p. 37
Boolean operations	p. 40
The Pumping Lemma	p. 45
Summary of Chapter 2	p. 48
Remarks on Chapter 2	p. 49
Non-deterministic automata	p. 53
Accessible automata	p. 53
Non-deterministic automata	p. 60
Applications	p. 67
Trim automata	p. 72
Grammars	p. 76
Summary of Chapter 3	p. 83
Remarks on Chapter 3	p. 83
[varepsilon]-automata	p. 85
Automata with [varepsilon]-transitions	p. 85
Applications of [varepsilon]-automata	p. 90
Summary of Chapter 4	p. 95
Remarks on Chapter 4	p. 95
Kleene's Theorem	p. 97
Regular languages	p. 97
Kleene's theorem: proof	p. 103
Kleene's theorem: algorithms	p. 106
Language equations	p. 114
Summary of Chapter 5	p. 125
Remarks on Chapter 5	p. 125
Local languages	p. 127
Myhill graphs	p. 127
Linearisation	p. 134
Summary of Chapter 6	p. 139
Remarks on Chapter 6	p. 139
Minimal automata	p. 141
Partitions and equivalence relations	p. 141
The indistinguishability relation	p. 144
Isomorphisms of automata	p. 152
The minimal automaton	p. 155
The method of quotients	p. 157
Summary of Chapter 7	p. 168
Remarks on Chapter 7	p. 168
The transition monoid	p. 171
Functions on states	p. 171
The extended transition table	p. 176
The Cayley table of an automaton	p. 183
Semigroups and monoids	p. 185
Summary of Chapter 8	p. 188
Remarks on Chapter 8	p. 189
The syntactic monoid	p. 191
Introduction to semigroups	p. 191
Congruences	p. 198
The transition monoid of an automaton	p. 207
The syntactic monoid of a language	p. 209
Summary of Chapter 9	p. 213
Remarks on Chapter 9	p. 214
Algebraic language theory	p. 217
Finite semigroups	p. 217
Recognisability by a monoid	p. 224
Two counterexamples	p. 231
Summary of Chapter 10	p. 234
Remarks on Chapter 10	p. 234
Star-free languages	p. 235
Introduction	p. 235
Groups	p. 238
Aperiodic semigroups	p. 249
Schutzenberger's theorem	p. 252
An example	p. 258
Summary of Chapter 11	p. 261
Remarks on Chapter 11	p. 262
Varieties of languages	p. 265
Pseudovarieties and varieties	p. 265
Equations for pseudovarieties	p. 273
Summary of Chapter 12	p. 276
Remarks on Chapter 12	p. 276
Discrete mathematics	p. 279
Logic and proofs	p. 279
Set theory	p. 281
Numbers and matrices	p. 285
Graphs	p. 287
Functions	p. 288
Relations	p. 290
Bibliography	p. 293
Index	p. 303
Table of Contents provided by Rittenhouse. All Rights Reserved.