Finite Automata
Purchasing Options
Features
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.
Table of Contents
INTRODUCTION TO FINITE AUTOMATA
Alphabets and Strings
Languages
Language Operations
Finite Automata: Motivation
Finite Automata and their Languages
Summary of Chapter 1
Remarks on Chapter 1
RECOGNISABLE LANGUAGES
Designing Automata
Incomplete Automata
Automata which Count
Automate which Locate Patterns
Boolean Operations
The Pumping Lemma
Summary of Chapter 2
Remarks on Chapter 2
NON-DETERMINISTIC AUTOMATA
Accessible Automata
Non-Deterministic Automata
Applications
Trim Automata
Grammars
Summary of Chapter 3
Remarks on Chapter 3
e-AUTOMATA
Automata withe-Transitions
Applications of e-Automata
Summary of Chapter 4
Remarks on Chapter 4
KLEENE'S THEOREM
Regular Languages
Kleene's Theorem: Proof
Kleene's Theorem: algorithms
Language Equations
Summary of Chapter 5
Remarks on Chapter 5
LOCAL LANGUAGES
Myhill Graphs
Linearisation
Summary of Chapter 6
Remarks on Chapter 6
MINIMAL AUTOMATA
Partitions and Equivalence Relations
The Indistinguishability Relation
Isomorphisms of Automata
The Minimal Auomaton
The Method of Quotients
Summary of Chapter 7
Remarks on Chapter 7
THE TRANSITION MONOID
Functions on States
The Extended Transition Table
The Cayley Table of an Automaton
Semigroups and Monoids
Summary of Chapter 8
Remarks on Chapter 8
THE SYNTACTIC MONOID
Introduction to Semigroups
Congruences
The Transition Monoid of an Automaton
The Syntactic Monoid of a Language
Summary of Chapter 9
Remarks on Chapter 9
ALGEBRAIC LANGUAGE THEORY
Finite Semigroups
Recognisability by a Monoid
Two Counterexamples
Summary of Chapter 10
Remarks on Chapter 10
STAR-FREE LANGUAGES
Introduction
Groups
Aperiodic Semigroups
Schutzenberger's Theorem
An Example
Summary of Chapter 11
Remarks on Chapter 11
VARIETIES OF LANGUAGES
Pseudovarieties and Varieties
Summary of Chapter 12
Remarks on Chapter 12
APPENDIX: DISCRETE MATHEMATICS
Logic and Proofs
Set Theory
Numbers and Matrices
Graphs
Functions
Relations
BIBLIOGRAPHY
INDEX
Editorial Reviews
“… this book provides a well-motivated introduction to the mathematical theory of finite automata. … 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 the book provides a route to understanding that you can tailor to their particular tastes and abilities. ”
— In Zentralblatt MATH, Vol. 1086, 2006/12
“Lawson’s book … is well written, self-contained, and quite extensive. The material is fully explained, with many examples fully discussed, and with many and varied exercises. … Students using this book will get a broad education in finite-automata theory.”
— SIAM Review
“[This book] is a nice textbook intended for an undergraduate lecture. … All presented results are illustrated by many simple examples. … The book is self-contained and easy to read. It can be recommended as a textbook for undergraduate lectures about finite automata.”
— EMS Newsletter
