You are previewing Elements of Automata Theory.
O'Reilly logo
Elements of Automata Theory

Book Description

Automata theory lies at the foundation of computer science, and is vital to a theoretical understanding of how computers work and what constitutes formal methods. This treatise gives a rigorous account of the topic and illuminates its real meaning by looking at the subject in a variety of ways. The first part of the book is organised around notions of rationality and recognisability. The second part deals with relations between words realised by finite automata, which not only exemplifies the automata theory but also illustrates the variety of its methods and its fields of application. Many exercises are included, ranging from those that test the reader, to those that are technical results, to those that extend ideas presented in the text. Solutions or answers to many of these are included in the book.

Table of Contents

  1. Cover
  2. Title
  3. Copyright
  4. Table of Contents
  5. Preface to the English Edition
  6. Preface
  7. M. Pascal’s Division Machine
  8. 0 Fundamental Structures
    1. 1 Relations
    2. 2 Monoids
    3. 3 Words and languages
    4. 4 Free monoids
    5. 5 Semirings
    6. 6 Matrices
    7. 7 Lexicon of graph theory
    8. 8 Complexity and decidability
    9. Solutions to the exercises
    10. Notes & references
  9. The three stages of rationality
    1. I The Simplest Possible Machine. . .
      1. 1 What is an ‘automaton’?
        1. 1.1 First definitions – first examples
          1. States, transitions, etc.
          2. Computations, recognised languages etc.
          3. Transposition and left–right duality
        2. 1.2 Basic constructions, basic properties
          1. Union
          2. Cartesian product
          3. Quotient (of a language)
        3. 1.3 The graph perspective
          1. Trim automata
          2. The empty and the infinite
          3. Criteria for recognisability
        4. 1.4 Some supplementary definitions
          1. Unambiguous automata
          2. Complete automata
          3. Deterministic automata
          4. Automata with spontaneous transitions
      2. 2 Rational languages
        1. 2.1 Rational operations
          1. Product of languages
          2. Star of a language
          3. Rational operations
        2. 2.2 Rational languages
        3. 2.3 Rational is recognisable
          1. Normalised automata
          2. Closure under product and star
          3. Standard automata
        4. 2.4 Recognisable is rational
          1. The McNaughton–Yamada algorithm, or algorithm MN Y
          2. The state elimination method
          3. Solving equations
      3. 3 The functional perspective
        1. 3.1 From transitions to the transition function
        2. 3.2 Deterministic automata
          1. Reformulation of the definition
          2. Determinisation
          3. The case of one-letter alphabets
          4. Complement of recognisable languages
        3. 3.3 Minimisation
          1. The automaton of quotients of a language. . .
          2. . . .is minimal
          3. Computation of the minimal automaton
          4. Another minimisation method
        4. 3.4 Return to the Star Lemma
          1. Block iteration and block simplification
          2. Ramsey’s Theorem
          3. Proof of Theorem 3.3
      4. 4 Rational expressions
        1. 4.1 Rational expressions and languages
          1. Rational expressions over an alphabet
          2. Rational expressions over a set0 of variables
        2. 4.2 Rational identities
          1. Classical identities
          2. A formal computation
        3. 4.3 Expressions for the behaviour of a finite automaton
          1. The state elimination and equation solution methods
          2. The B MC and MNY algorithms, identical orders
          3. The BMC and MNY algorithms, distinct orders
        4. 4.4 Derivation of expressions
          1. Derivatives of an expression
          2. A theorem of J. Brzozowski
          3. Derivative automaton
      5. 5 From expressions to automata
        1. 5.1 The standard automaton of an expression
          1. Direct construction
          2. Thompson’s construction
        2. 5.2 The derived term automaton
          1. Derived terms
          2. A theorem of V. Antimirov
        3. 5.3 String matching
          1. Automaton for finding a word
          2. Searching by sliding window
          3. Implementation with a default successor
      6. 6 Star height
        1. 6.1 Two heights and a degree
          1. Star height of an expression
          2. Star height of a language
          3. Loop complexity of an automaton
        2. 6.2 Eggan’s Theorem
          1. From expressions to automata
          2. From automata to expressions: calculating the index
          3. Not so fast
        3. 6.3 An infinite hierarchy
        4. 6.4 Generalised star height
      7. 7 A field of automata
        1. 7.1 The Rabin–Scott model
        2. 7.2 Two-way automaton
        3. 7.3 Moore and Mealy machines
      8. 8 A crop of properties
      9. Solutions to the exercises
      10. Notes & references
    2. II The Power of Algebra
      1. 1 Automata and rational sets
        1. 1.1 Automata over a monoid
        2. 1.2 Rational sets
          1. The semiring b(M)
          2. Rational operations and subsets
          3. Rational expressions
          4. Image under morphism
          5. Intersection and inverse morphism
        3. 1.3 Behaviour of finite automata
        4. 1.4 Unambiguous rational sets
          1. Definitions
          2. The family URat
      2. 2 Actions and recognisable sets
        1. 2.1 Actions on a set
          1. Definition
          2. Matrix representation of actions
          3. Subsets recognised by an action
        2. 2.2 Recognisable here, recognisable there
          1. Consistency
          2. Kleene’s Theorem
          3. Automaton of an action
        3. 2.3 Elementary operations on recognisable subsets
          1. Boolean operations
          2. Inverse morphism
          3. Quotient
          4. Morphism and product
        4. 2.4 Minimisation
          1. Action morphisms
          2. Minimal action
          3. Syntactic congruence and monoid
        5. 2.5 Algebra at work
          1. Two examples
          2. Recognisable subsets included in a product
      3. 3 Morphisms and coverings
        1. 3.1 Automata morphisms
          1. Definitions and examples
          2. Conformal morphisms
          3. Local properties
        2. 3.2 Quotients of automata
          1. Out-surjective morphisms
          2. Totally surjective morphisms
          3. Moore’s algorithm
        3. 3.3 Automata coverings
          1. From local to global
          2. Product of an automaton with an action
          3. The Coloured Transition Lemma
        4. 3.4 The Schützenberger covering
      4. 4 Universal automaton
        1. 4.1 Factorisations
          1. 2-factorisations
          2. Sub-factorisations and factorisations
          3. Morphisms and factorisations
        2. 4.2 Universal automata of a subset
          1. Definitions and examples
          2. Properties
          3. Universal automaton relative to a generating set
          4. Universality of universal automata
        3. 4.3 Construction of the universal automaton
          1. Expansion of a deterministic automaton
          2. Extraction of the universal automaton
        4. 4.4 Language approximations
      5. 5 The importance of being well ordered
        1. 5.1 Well quasi-orderings
        2. 5.2 Derivations
          1. Preparations
          2. Proof of Theorem 5.4
      6. 6 Rationals in the free group
        1. 6.1 Recognisable and rational in groups
          1. Recognisable subsets
          2. Rational subgroups
          3. Fatou property
        2. 6.2 Description of the free group
          1. Dyck congruence and Dyck words
          2. Shamir congruence and parenthetic words
          3. Simplifications
          4. Reduction associated with a simplification
          5. Unambiguous factorisation induced by a reduction
        3. 6.3 Rationals of the free group
          1. Rationals of simplification monoids
          2. Return to the free group
        4. 6.4 Büchi systems
      7. 7 Rationals in commutative monoids
        1. 7.1 The natural order on A⊕
          1. The free commutative monoid
          2. Dickson’s Lemma
        2. 7.2 The lexicographic order on nk
          1. Congruences of nk
          2. Lexicographic decomposition
        3. 7.3 Subtractive submonoids and affine sets
        4. 7.4 Semi-linear and semi-simple sets
        5. 7.5 Rationals of nk
          1. The Freedom Lemma
          2. Positive solutions of Diophantine linear systems
          3. Semi-simple subsets of zk
          4. Proof of Theorems 7.3 and 7.4
        6. 7.6 Rationals of commutative monoids
      8. 8 Star height of group languages
      9. Solutions to the exercises
      10. Notes & references
    3. III The Pertinence of Enumeration
      1. 1 Formal power series on a graded monoid
        1. 1.1 Formal power series over M with coefficients in z
          1. Operations on k
          2. Support of a series
          3. characteristic series
          4. Hadamard product
          5. Scalar product
        2. 1.2 Graded monoids
        3. 1.3 Topology on km
          1. Distance
          2. Distance on km
          3. Summable families
          4. Continuous morphisms
      2. 2 k-automata and k-rational power series
        1. 2.1 Star of a power series
          1. Star in a topological semiring
          2. Star of a proper series
          3. Star of an arbitrary series
        2. 2.2 k-rational series
          1. K-rational operations
          2. Rational K-expressions
          3. Star of a matrix
        3. 2.3 Weighted automaton in a semiring
          1. K-automaton over M
          2. Behaviour of a K-automaton
          3. Notes
          4. Some other definitions and examples
        4. 2.4 The Fundamental Theorem of finite automata
          1. Proper automata
          2. proper families of series
          3. Statement and proof
          4. Notes and corollaries
        5. 2.5 k-coverings k-quotients
          1. From coverings to k-coverings
          2. Matrix description
          3. Co-K-covering
          4. Minimal K-quotient
      3. 3 k-recognisable series
        1. 3.1 k-representations
        2. 3.2 Products
          1. Tensor product of k-representations
          2. Hadamard product
          3. Tensor product of series
          4. Shuffle product
        3. 3.3 The Kleene-Schützenberger Theorem
      4. 4 Series on a free monoid
        1. 4.1 A characterisation of recognisable series
          1. Quotients of series
          2. Stable modules
          3. The Kleene-Schützenberger Theorem revisited
        2. 4.2 Derivation of rational k-expressions
          1. Polynomials of k-expressions
          2. k-derivatives of a k-expression
          3. Derived terms
          4. The derived term automaton
        3. 4.3 Series on a field
          1. Rank of a series
          2. Reduced representation
          3. Linear recurrence
          4. Effective computations
        4. 4.4 Rational series and their supports
          1. Rationality of supports
          2. The Rational Skimming Theorem, I
          3. Undecidable questions
      5. 5 Series on an arbitrary monoid
        1. 5.1 Complete semirings, continuous semirings
        2. 5.2 Star of a series
        3. 5.3 k-rational series
      6. 6 Rational subsets in free products
        1. 6.1 Free product of monoids
        2. 6.2 Bipartite automaton over a free product
        3. 6.3 Bipartite deterministic automaton
        4. 6.4 Minimal deterministic bipartite automaton
      7. 7 A non-commutative linear algebra primer
      8. Solutions to the exercises
      9. Notes & references
  10. Rationality in relations
    1. IV The Richness of Transducers
      1. 1 Rational relations: an introduction
        1. 1.1 Rational relations
          1. Rational relations between free monoids
          2. Rational relations between arbitrary monoids
        2. 1.2 Realisation by automata
        3. 1.3 Realisation by morphisms
          1. Realisation
          2. Evaluation Theorem
          3. Composition Theorem
          4. Star Lemma
        4. 1.4 Recognisable relations
        5. 1.5 Realisation by representation
          1. Real-time transducers
          2. From real-time transducers to representations
          3. Theorem of evaluation and composition of representations
        6. 1.6 The Rabin–Scott model
      2. 2 k-relations
        1. 2.1 Definitions
          1. The canonical isomorphism
          2. k-relations
          3. Support of relations – characteristic relations
          4. Continuity
        2. 2.2 Composition
        3. 2.3 Multiplicative k-relations
      3. 3 Rational k-relations
        1. 3.1 Reasonable semirings.
          1. Image of series under continuous morphisms
          2. Image of seres under projections
          3. k-intersections
        2. 3.2 Realisation of rational k-relations
          1. Realisation by k-automaton
          2. Realisation by k-representation
          3. Realisation by morphisms
        3. 3.3 Evaluation and Composition Theorems
          1. Using recognition by morphisms
          2. Using recognition by representation
      4. 4 Equivalence of finite k-transducers
        1. 4.1 Equivalence of b-transducers, general case
        2. 4.2 Equivalence of b-transducers, case of small alphabets
        3. 4.3 Equivalence of n-transducers
      5. 5 Deterministic rational relations
        1. 5.1 Transducers with an endmarker
        2. 5.2 Deterministic transducers
          1. Definition
          2. Uniqueness of computations
          3. Almost an action
        3. 5.3 Deterministic relations
          1. Definitions
          2. Complement
          3. Iteration Lemma
        4. 5.4 Geography of Rat A* × B* I
        5. 5.5 Matrix representations
          1. Representation of a deterministic transducer
          2. Representation of a deterministic relation
        6. 5.6 An example: the map equivalence of a morphism
      6. 6 Synchronisation of transducers
        1. 6.1 Rational relations of bounded length discrepancy
          1. Definitions, notation and conventions
          2. Characterisation of rational bld-relations
          3. Translation into automata theoretic terms, and corollaries
        2. 6.2 Transducers of bounded lag
          1. Lag in a computation or transducer
          2. Resynchronisation algorithm for transducers
          3. Composition of letter-to-letter transducers
        3. 6.3 Synchronous relations
          1. Another family of rational relations
          2. Determinisation and minimisation
          3. Geography of Rat A* × B* II
      7. 7 Malcev-Neumann series
        1. 7.1 Order on the free group
          1. On ordered groups
          2. Representation of the free group
          3. A detour via ordered rings
          4. Order on the free group
        2. 7.2 Series on an ordered group
          1. The semiring kwog
          2. Ordered semigroups
          3. The field kwog
          4. A last inclusion
      8. Solutions to the exercises
      9. Notes & references
    2. V The Simplicity of Functional Transducers
      1. 1 Functionary
        1. 1.1 Deciding functionality
          1. An effective characterisation of functionality
          2. Equivalence of rational functions
        2. 1.2 Sequential functions
          1. Some unconventional terminology
          2. Dual definitions
          3. Composition
        3. 1.3 Pure sequential functions
        4. 1.4 Local functions
      2. 2 Uniformisation of rational relations
        1. 2.1 Proof of Theorem 2.1 (transducer version)
        2. 2.2 Proof of Theorem 2.1 (representation version)
          1. Represent of S-immersions of an automaton
          2. Semi-monomial matrices
          3. Representation of S-uniformisations
        3. 2.3 Decomposition of rational functions
          1. The Weak Decomposition Theorem
          2. The Strong Decomposition Theorem
        4. 2.4 The Rational Skimming Theorem II
      3. 3 Cross-section of rational functions
        1. 3.1 The rational cross-section property
          1. The Rational Cross-Section Theorem
          2. The rational cross-section property for a monoid
          3. Return to simplification monoids
        2. 3.2 Choosing the uniformisation (or the cross-section)
          1. Uniformisation of synchronous relations
          2. Uniformisation of deterministic relations
          3. Th. 3.3 back on the loom
      4. 4 Sequential functions
        1. 4.1 Two characterisations
          1. Translations of a function
          2. A functional characterisation
          3. A quasitopological point of view
        2. 4.2 Deciding sequentiality
        3. 4.3 Minimisation
          1. Conjugation
          2. Blockage of a sequential transducer
          3. Reduction
          4. Effective computation
        4. 4.4 The (Great) Sequentiality Theorem
          1. Differential of a function
          2. Proof of Theorem 4.5 iii) ⇒ i)
          3. Proof of Theorem 4.5 ii) ⇒ iii)
          4. Return to the Sequentiality Theorem
        5. 4.5 Pure sequential functions and local functions
        6. Solutions to the exercises
        7. Notes & references
  11. Bibliography
  12. Index