Un automate (au pluriel : automates) — parfois appelé machine à états — est un modèle mathématique abstrait qui décrit comment un système peut évoluer d'un état à un autre en fonction d'entrées. Il sert à modéliser des comportements discrets : réception d'un signal, analyse d'un mot, contrôle d'un dispositif, etc.

On peut voir l'automate comme une machine qui lit une suite de symboles (une entrée). À chaque symbole lu, l'automate peut changer d'état selon des règles appelées transitions. Quand la lecture est terminée, l'automate se trouve dans un état donné : si cet état est un état final, l'entrée est acceptée, sinon elle est rejetée. Une image concrète : un distributeur automatique qui accepte ou rejette les pièces et délivre (ou non) un produit selon la somme insérée.

Définition formelle (automate fini déterministe)

Un automate fini déterministe (souvent abrégé DFA en anglais) est formellement défini par un 5‑uplet (Q, Σ, δ, q0, F), où :

  • Q est un ensemble fini d'états ;
  • Σ est un alphabet fini (ensemble de symboles d'entrée) ;
  • δ : Q × Σ → Q est la fonction de transition (elle indique pour chaque état et symbole l'état suivant) ;
  • q0 ∈ Q est l'état initial ;
  • F ⊆ Q est l'ensemble des états acceptants (ou finaux).

Lecture et acceptation : l'automate commence en q0 et lit les symboles un par un. Après lecture complète de la chaîne, si l'état courant appartient à F, la chaîne est acceptée.

Variantes importantes

  • Automate fini non déterministe (NFA) : la fonction de transition peut renvoyer plusieurs états possibles, et on autorise souvent des transitions ε (sans lire de symbole). Les NFA et DFA reconnaissent exactement les mêmes langages (les langages réguliers).
  • Automates à pile (pushdown automata) : possèdent une pile et reconnaissent les langages context‑free (ex. {a^n b^n}).
  • Machines de Turing : modèles plus puissants capables de simuler tout calcul effectif (langages récursifs et récursivement énumérables).

Diagrammes d'états

Un diagramme à états finis représente graphiquement un automate :

  • chaque état est un nœud (un cercle) ;
  • l'état initial est indiqué par une flèche entrant dans son état sans origine ;
  • les états finaux sont dessinés en double cercle ;
  • les transitions sont des flèches étiquetées par le(s) symbole(s) qui provoquent le passage d'un état à un autre.

Exemple simple : un automate qui reconnaît les mots sur {0,1} contenant un nombre pair de 1. Il a deux états : pair (initial et acceptant) et impair. À chaque lecture d'un 1, on bascule entre pair et impair. La lecture d'un 0 laisse l'état inchangé.

Exemples concrets

  • Distributeur automatique : états = sommes partielles, transitions = insertion de pièces, états finaux = sommes permettant la délivrance du produit. Pièces non reconnues = rejet. Cet exemple illustre un modèle simple mais pratique.
  • Reconnaissance d'un motif : un automate peut vérifier si une chaîne contient la sous-chaîne «ab» ou s'achève par «01». Il sert de base pour les expressions régulières simples.
  • Contrôle de protocole : modélisation des états d'une connexion réseau (ouvert, en attente, fermé) et des messages qui provoquent des transitions.

Propriétés et utilisations

  • Langages réguliers : les automates finis reconnaissent exactement les langages réguliers, décrits aussi par des expressions régulières et par certaines grammaires régulières.
  • Équivalence DFA/NFA : tout NFA peut être transformé en un DFA équivalent (construction de l'ensemble des états), bien que le DFA résultant puisse être exponentiellement plus grand.
  • Applications pratiques : analyse lexicale (compilateurs), moteurs de recherche de motifs, validation de protocoles, circuits de contrôle, vérification formelle.
  • Limites : un automate fini ne peut pas mémoriser un nombre non borné d'informations (par exemple reconnaître le langage {a^n b^n | n ≥ 0} n'est pas possible avec un automate fini).

Conseils pour lire ou dessiner un diagramme

  • Repérez l'état initial et les états finaux (double cercle).
  • Suivez la lecture d'une chaîne symbole par symbole en parcourant les transitions correspondantes.
  • Pour un NFA, la machine accepte si au moins un parcours possible aboutit à un état final.

En résumé, un automate (ou machine à états) est un modèle fondamental et simple pour représenter des systèmes discrets : il possède un nombre fini d'états, des transitions gouvernées par des symboles d'entrée, et une règle d'acceptation basée sur des états finaux. De nombreux outils pratiques et théoriques en informatique reposent sur ce concept.