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