É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 , d'un
ensemble fini d'états
, d'une relation de transition,
sous-ensemble de
, d'un état initial
et
d'un ensemble d'états finaux
. Une transition
, dite de l'état
vers l'état
et étiquetée par le symbole
, est notée
. Un calcul de cet automate
est une suite de transitions
; ce calcul
est réussi si le dernier état,
, est un état final, et on
dit alors que le mot
est reconnu par
l'automate fini.
Un langage est régulier s'il existe un automate fini dont
l'ensemble des mots reconnus est exactement
. 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
. 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 à états 0 (initial), 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 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
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.