Introduction

Les automates sont des machines qui permettent d’exécuter des algorithmes (ou faire des calculs) très simples et omniprésents en informatique.

On formalise l’exécution d’un automate par la reconnaissance d’un langage, c’est-à-dire un ensemble de mots. Cela apparait dans les domaines suivants :

  • analyse sémantique (parsing)
  • compilateurs
  • contrôleurs

Le mot vient du grec et signifie littéralement “qui agit tout seul” et cela se retrouve dans le fait que les automates (au sens informatique) peuvent modéliser les automates concrets comme les distributeurs automatiques de café ou les photomatons.

La puissance de calcul (au sens de ce que l’on peut faire avec) des automates est plus limitée que les machines de Turing. Cela est essentiellement au nombre d’états finis qui limite les capacités mémoires. Cependant, pour des tâches particulières, les automates sont souvent plus efficaces et économes en ressource.

Les expressions régulières (REGEX) sont aussi très courantes en informatique. Nous verrons que les automates et les expressions régulières sont en fait en correspondance et reconnaissent les mêmes langages.