Automates finis

Étudiés par Kleene au début des années 50, les automates finis furent auparavant utilisés par McCulloch et Pitts comme un modèle << neuronal >> de calcul et par Shannon pour décrire le comportement d'un canal de communication.

Un automate fini est défini par la donnée d'un alphabet $A$, d'un ensemble fini d'états $E$, d'une relation de transition, sous-ensemble de $E\times A \times E$, d'un état initial $I\in E$ et d'un ensemble d'états finaux $F\subseteq E$. Une transition $(e, a, e')$, dite de l'état $e$ vers l'état $e'$ et étiquetée par le symbole $a$, est notée $e\stackrel{a}{\to} e'$. Un calcul de cet automate est une suite de transitions $I = e_{1} \stackrel{a_{1}}{\to} e_{2} \stackrel{a_{2}}{\to} \cdots \stackrel{a_{n-1}}{\to} e_{n}$ ; ce calcul est réussi si le dernier état, $e_n$, est un état final, et on dit alors que le mot $a_{1}a_{2}\cdots a_{n-1}$ est reconnu par l'automate fini.

Un langage $X$ est régulier s'il existe un automate fini dont l'ensemble des mots reconnus est exactement $X$. On montre qu'il existe alors un automate fini déterministe et complet (c'est-à-dire, pour tout état, il existe exactement une transition par symbole de l'alphabet) reconnaissant $X$. Ces automates finis peuvent être vus comme des machines abstraites, parmi les plus simples, puisqu'elles n'utilisent pas de mémoire, dont le fonctionnement est facile à simuler à l'aide d'un programme.

Un automate fini déterministe à $N$ états 0 (initial), 1, ..., $N-1$, et dont les transitions sont étiquetées par des valeurs de type char, peut être implémenté au moyen des deux structures mutuellement récursives suivantes :

struct state {
  bool final;
  transition *transitions; 
};
struct transition {
  char symbol;
  state *to;  
  transition *next; 
};
typedef state *automaton[N];

Ainsi, un état est représenté à l'aide d'un pointeur s vers un objet de type state : s->final indique si l'état est final (false si non final, et true si final), et ses transitions sont organisées en une liste chaînée de tête s->transitions. Une transition, si elle est représentée par un pointeur t vers un objet de type transition, comporte comme information son étiquette t->symbol, l'état t->to auquel elle conduit, et la transition suivante t->next dans la liste. L'automate sera ensuite représenté par un tableau de $N$ pointeurs de state.

Un important résultat de la théorie des langages est dû à Kleene (1956) : un langage est reconnaissable par un automate fini si et seulement s'il est rationnel. Par exemple, le langage défini par l'expression rationnelle $a^\star bb(a\vert b)^\star$ est reconnu par l'automate déterministe de la figure 32. C'est ainsi que sont réalisées les opérations de recherche de la commande egrep d'Unix.