Automates finis

18.1 Introduction et motivation

Comment décider, mécaniquement, si un mot appartient à un langage — les mots se terminant par a, ceux ayant un nombre pair de a, ceux contenant le motif ab ? L'outil fondamental est l'automate fini : une machine à un nombre fini d'états, qui lit le mot lettre par lettre et change d'état selon des transitions. Le mot est accepté si, une fois lu, la machine se trouve dans un état acceptant.

Ce chapitre, en ouverture du cours, est une belle synthèse : un automate se modélise par un enregistrement (chapitre 7) contenant un tableau de transitions (chapitre 5) ; la reconnaissance lit une chaîne (chapitre 6) ; tester si le langage est vide est une question d'accessibilité dans un graphe (chapitre 15) ; et compter les mots acceptés relève de la programmation dynamique (chapitre 13).

18.2 Représenter un automate

On considère un automate fini déterministe (AFD) complet : un état initial, des états acceptants, et pour chaque état et chaque lettre, exactement une transition. Les états sont numérotés 0..n-1, les lettres codées par des indices 0..k-1.

type automate = {
  nb_etats : int;
  initial : int;
  acceptants : bool array;        (* acceptants.(e) = e est acceptant *)
  delta : int array array;        (* delta.(etat).(lettre) = état suivant *)
}