Automata

Jean-Éric Pin



Résumé : Le but de ce chapitre est d'introduire plusieurs notions et résultats fondamentaux de la théorie des automates. Nous définissons d'abord les automates finis et les langages reconnaissables. Puis nous explorons les propriétés de base des automates finis (déterministe, complet, accessible, standard, etc.) et nous décrivons les opérations standard sur les langages (opérations booléennes, produit de concaténation, étoile, quotients, etc.) Nous définissons ensuite l'automate minimal d'un langage et sa contrepartie algébrique, le monoïde syntaxique et sa version ordonnée. Nous prouvons le théorème de Kleene en utilisant l'algorithme de Glushkov dans un sens et les équations linéaires dans l'autre sens. Dans la dernière section, nous définissons brièvement les sous-ensembles rationnels et reconnaissables de monoïdes arbitraires.

Abstract : The aim of this chapter is to introduce several fundamental notions and results of automata theory. We first define finite automata and recognizable languages. Then we explore the basic properties of finite automata (deterministic, complete, accessible, standard, etc.) and we describe the standard opertions on languages (Boolean operations, concatenation product, star, quotients, etc.). Then we define the minimal automaton of a language and its algebraic counterpart, the syntactic monoid and its ordered version. We prove Kleene's theorem using Glushkov's algorithm in one direction and linear equations for the other direction. In the last section we briefly define rational and recognizable subsets of arbitrary monoids.

PostScript gzipped file, PDF file