| Description |
1 online resource : text file, PDF |
| Contents |
Cover; Title Page; Copyright Page; Dedication; Table of Contents; Preface; 1: Introduction to finite automata; 1.1 Alphabets and strings; 1.2 Languages; 1.3 Language operations; 1.4 Finite automata: motivation; 1.5 Finite automata and their languages; 1.6 Summary of Chapter 1; 1.7 Remarks on Chapter 1; 2: Recognisable languages; 2.1 Designing automata; 2.2 Incomplete automata; 2.3 Automata that count; 2.4 Automata that locate patterns; 2.5 Boolean operations; 2.6 The Pumping Lemma; 2.7 Summary of Chapter 2; 2.8 Remarks on Chapter 2; 3: Non-deterministic automata; 3.1 Accessible automata |
|
3.2 Non-deterministic automata3.3 Applications; 3.4 Trim automata; 3.5 Grammars; 3.6 Summary of Chapter 3; 3.7 Remarks on Chapter 3; 4: ɛ-automata; 4.1 Automata with e-transitions; 4.2 Applications of ɛ-automata; 4.3 Summary of Chapter 4; 4.4 Remarks on Chapter 4; 5: Kleene's Theorem; 5.1 Regular languages; 5.2 Kleene's theorem: proof; 5.3 Kleene's theorem: algorithms; 5.4 Language equations; 5.5 Summary of Chapter 5; 5.6 Remarks on Chapter 5; 6: Local languages; 6.1 My hill graphs; 6.2 Linearisation; 6.3 Summary of Chapter 6; 6.4 Remarks on Chapter 6; 7: Minimal automata |
|
7.1 Partitions and equivalence relations7.2 The indistinguishability relation; 7.3 Isomorphisms of automata; 7.4 The minimal automaton; 7.5 The method of quotients; 7.6 Summary of Chapter 7; 7.7 Remarks on Chapter 7; 8: The transition monoid; 8.1 Functions on state; 8.2 The extended transition table; 8.3 The Cayley table of an automaton; 8.4 Semigroups and monoids; 8.5 Summary of Chapter 8; 8.6 Remarks on Chapter 8; 9: The syntactic monoid; 9.1 Introduction to semigroups; 9.2 Congruences; 9.3 The transition monoid of an automaton; 9.4 The syntactic monoid of a language |
|
9.5 Summary of Chapter 99.6 Remarks on Chapter 9; 10: Algebraic language theory; 10.1 Finite semigroups; 10.2 Recognisability by a monoid; 10.3 Two counterexamples; 10.4 Summary of Chapter 10; 10.5 Remarks on Chapter 10; 11: Star-free languages; 11.1 Introduction; 11.2 Groups; 11.3 Aperiodic semigroups; 11.4 Schiitzenberger's theorem; 11.5 An example; 11.6 Summary of Chapter 1; 11.7 Remarks on Chapter 11; 12: Varieties of languages; 12.1 Pseudovarieties and varieties; 12.2 Equations for pseudovarieties; 12.3 Summary of Chapter 12; 12.4 Remarks on Chapter 12; A: Discrete mathematics |
|
A.1 Logic and proofsA. 2 Set theory; A.3 Numbers and matrices; A.4 Graphs; A.5 Functions; A.6 Relations; Bibliography; Index |
| 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."--Provided by publisher |
| Subject |
Combinatorial analysis.
|
|
Algebra.
|
|
Computer science -- Mathematics.
|
|
algebra.
|
|
MATHEMATICS -- Algebra -- General.
|
|
MATHEMATICS -- Combinatorics.
|
|
Algebra
|
|
Combinatorial analysis
|
|
Computer science -- Mathematics
|
| Form |
Electronic book
|
| ISBN |
9781482258097 |
|
1482258099 |
|
