Résumé : Il s'agit d'un chapitre
de la section I/9, Algorithmique et Programmation, de l'Encyclopédie de
l’informatique et des systèmes d’information.
Cette section de l'encyclopédie est consacrée à trois outils
fondamentaux de l'informatique: l'algorithmique, les modèles de
machine et les langages de programmation.
Introduits vers 1950, les automates finis constituent le
modèle le plus élémentaire de machine. Ce chapitre présente d'une part
les automates usuels, qui se contentent de lire un mot en entrée pour
l'accepter ou le rejeter, et les automates séquentiels, munis d'une
entrée et d'une sortie. Après une brève présentation du théorème de
Kleene, clé de voûte de la théorie des automates, nous décrivons les
applications des automates dans divers domaines, notamment la
modélisation et les industries de la langue.
Abstract : This is the introduction to Section
I/9, Algorithms and Programming, of the Encyclopaedia of Computer
Science and Information Systems.
This section is devoted to three fundamental tools in computer science:
algorithms, machine models and programming languages.
Introduced around 1950, finite automata form the most elementary model of
machine. This chapter presents automata in the usual sense, that accept or
reject a given word and sequential automata, that produce an output.
After a brief presentation of Kleene's theorem, the cornerstone of the
theory of automata, we describe applications in various domains, notably
their use as a verification model and their applications to natural
languages.