Résumé : Il s'agit d'un article de synthèse sur
les automates finis et les langages reconnaissables. Il est destiné
principalement aux mathématiciens qui connaissent un peu la
théorie des semigroupes mais qui n'ont aucune connaissance en
théorie des automates et des langages. Les sujets traités
dans cet article couvrent le théorème de Kleene,
l'équivalence entre automates finis et semigroupes, les
différentes hiérarchies de langages (hiérarchies de
concaténation, hauteur d'étoile, etc.), la
caractérisation syntactique des langages sans-étoile, les
langages testables par morceaux et localement testables, le
théorème des variétés d'Eilenberg et un
aperçu des résultats récents.
Abstract : This paper is a survey on finite automata and
recognizable languages. It is written for the mathematician who has a
background in semigroup theory but knows next to nothing on automata and
languages. The topics covered in this paper include Kleene's theorem, the
equivalence between finite automata and finite semigroups, the various
hierarchies of languages (dot-depth, star-height, etc.), the syntactic
characterization of the star-free, the piecewise testable and the locally
testable languages, Eilenberg's variety theorem and a quick review of some
recent results.