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.

  

Figure 34: Un automate déterministe sur l'alphabet $\{a,b\}$, à quatre états, 0 est l'état initial, 2 est final

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 :

typedef struct {
  int final;
  struct transition *transitions; 
} state;
typedef struct transition {
  char symbol;
  state *to;  
  struct transition *next; 
} transition;
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 (0 si non final, et 1 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 34. C'est ainsi que sont réalisées les opérations de recherche de la commande egrep d'Unix.