Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle de processus, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. Par défaut une machine à états finis est non déterministe.
Notions Les automates finis (déterministes ou non) reconnaissent exactement des langages rationnels. Ce sont les machines les plus simples dans la hiérarchie de Chomsky, et par conséquent ils sont moins puissants que les automates à pile et, bien entendu, que les machines de Turing.
Un automate est constitué d'états stables et de transitions. Son comportement est dirigé par un mot machine fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. Dans l'exemple ci-contre, pour l'entrée , et si l'automate démarre en , il passe successivement par les états , le calcul correspondant est :
+ Table de transition L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. On peut très bien considérer des automates sans limitation sur le nombre d'états : la théorie qui en résulte est très analogue à la théorie habituelle. Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées. L'état initial est marqué par une flèche entrante ; un état final est, selon les auteurs, soit doublement cerclé (dans la figure 1 ci-dessus, l'état est à la fois initial et final), soit marqué d'une flèche sortante (dans la figure 2 ci-dessous, 1 est initial et 3 est final).
Une autre façon commode de représenter un automate fini est sa table de transition. Elle donne, pour chaque état et chaque lettre, l'état d'arrivée de la transition. Voici à droite la table de transition de l'automate de la figure 1 :
On distinguera les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automata ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Un automate est déterministe si, pour chacun de ses états, il y a au plus une transition pour chaque étiquette possible et si, de plus, il a un seul état initial. S'il a exactement une transition par étiquette, on parle alors d'automate déterministe complet. L'automate ci-dessus est déterministe et complet.
Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il est indifférent qu'il soit déterministe ou non.
Types
Il existe plusieurs types d'automates finis. Les « accepteurs » ou « reconnaisseurs » produisent en sortie une réponse « oui » ou « non », selon qu'ils acceptent (oui) ou rejettent (non) le mot présenté en entrée. Dans l'exemple ci-dessus (Fig. 1), le mot n'est pas accepté, mais le mot est accepté. D'autres automates classent l'entrée par catégorie : au lieu de répondre par oui ou par non, ils répondent par une classification ; de tels automates se rencontrent par exemple en linguistique. Les automates pondérés (weighted automata en anglais) associent à chaque mot une valeur numérique.
Les automates finis servent à caractériser des langages (c'est-à-dire des ensembles, finis ou non, de mots finis en général) : ce sont les langages composés des mots acceptés, ou langages reconnus par les automates. Des extensions des automates finis reconnaissent des langages de mots infinis. Ce sont les automates sur les mots infinis . Les plus connus d'entre eux sont les automates de Büchi), les automates de Muller. D'autres automates reconnaissent divers types d'arbres (automates d'arbres).
Dans les automates non déterministes, il peut y avoir plusieurs transitions à partir d'un état donné pour une étiquette donnée. Ici, le terme « non déterministe » ne signifie pas la négation de « déterministe » (c'est-à-dire « nécessairement non déterministe ») mais l'absence éventuelle de cette propriété (c'est-à-dire « non nécessairement déterministe »).
Il est remarquable que tout automate fini peut être transformé, au moyen d'une opération qui peut éventuellement augmenter exponentiellement son nombre d'états, en un automate déterministe : c'est la déterminisation expliquée plus loin.
Les automates finis se rencontrent, dans une formulations proche, dans les circuits intégrés numériques, où l'entrée, l'état et le résultat sont des vecteurs de taille fixe de bits. Les machines de Moore et machines de Mealy sont des automates finis avec sortie. Dans les machines de Moore, les actions sont liées aux états, tandis que dans les machines de Mealy les actions (sorties) sont liées aux transitions. Les transducteurs finis sont plus généraux comme automates avec sortie.
Définitions formelles
Alphabet Un alphabet est un ensemble, en général supposé fini et non vide. Ses éléments sont des lettres. Mot Un mot sur un alphabet est une suite finie d'éléments de . Un mot est noté par la juxtaposition de ses lettres. Ainsi, on écrit au lieu de . La longueur d'un mot est le nombre d'éléments qui le composent. La suite vide, mot de longueur 0, souvent notée , est appelée le mot vide. L'ensemble des mots sur est noté . La concaténation de deux mots et est le mot obtenu par juxtaposition. En particulier, . La concaténation est associative, et par conséquent , muni de la concaténation, est un monoïde.
Automate fini
thumb|Fig. 2 : Automate reconnaissant les mots finissant par . Un automate fini ou automate fini non déterministe (AFN) sur un alphabet est un quadruplet , où : est un ensemble fini d'états, est l'ensemble des transitions, est l'ensemble des états initiaux, et est un ensemble d'états finaux ou terminaux.
Une transition est composée d'un état de départ , d'un élément , appelé étiquette, et d'un état d'arrivée . Un calcul (on dit aussi un chemin ou une trace) est une suite de transitions consécutives :
Son état de départ est , son étiquette est le mot et son état d'arrivée est . Un calcul est réussi si son état de départ est un des états initiaux, et son état d'arrivée est un des états terminaux.
Un mot est reconnu ou accepté par l'automate s'il est l'étiquette d'un calcul réussi. Le langage reconnu par l'automate est l'ensemble des mots reconnus. Un langage est reconnaissable s'il est reconnu par un automate fini.
Le langage reconnu par un automate est dénoté généralement par .
Automate complet, automate émondé Un automate est complet si pour tout état , et pour toute lettre , il existe au moins une transition partant de et portant l'étiquette . Un état est accessible s'il existe un chemin d'un état initial à . Un état est coaccessible s'il existe un chemin de à un état final. Un automate est accessible (coaccessible) si tous ses états sont accessibles (coaccessibles). Un automate est émondé si tous ses états sont à la fois accessibles et coaccessibles.
Automate fini déterministe thumb|Fig. 3 : Automate reconnaissant les mots commençant par . Un automate fini déterministe (AFD) sur un alphabet est un automate fini qui vérifie les deux conditions suivantes : il possède un seul état initial ; pour tout état , et pour toute lettre , il existe au plus une transition partant de et portant l'étiquette .
Pour un automate déterministe, la fonction de transition est la fonction partielle définie par : si est une transition. Si la fonction de transition est partout définie, l'automate est complet. La fonction de transition est étendue en une application (partielle) en posant pour tout état . Ici dénote le mot vide. pour tout état , tout mot et toute lettre .
Variations de notations Il est d'usage de remplacer la notation par un simple point. On écrit alors à la place de , et la formule devient . Ceci montre aussi que la fonction de transition est une action du monoïde libre sur l'ensemble . On rencontre aussi la notation
pour un automate déterministe, la fonction de transition étant sous-entendue (comme la loi de composition dans un groupe, par exemple). L'automate de la figure 3 est déterministe et incomplet. Son état initial est , et il possède un seul état final, l'état . Il reconnaît le langage sur l'alphabet .
On rencontre dans la littérature l'écriture d'un automate fini général sous forme de quintuplet . Ici, l'alphabet de l'automate est inclus dans la spécification. La même façon d'inclure alphabet de définition dans la spécification se voit aussi pour les automates déterministes.
Exemples
L'automate du début de l'article reconnaît les écritures binaire des entiers naturels multiples de 3. Par exemple, le nombre 18, dont l'écriture binaire est , est reconnu : le calcul est . On peut se convaincre qu'un entier mène, depuis l'état initial, à , ou , selon que le reste de sa division par 3 est 0, 1, ou 2.
thumb|Automate reconnaissant les mots contenant un nombre impair de lettres . L'exemple suivant décrit un automate fini déterministe complet sur l'alphabet binaire , qui détermine si l'entrée contient un nombre impair de . Cet automate intervient dans la suite de Thue-Morse. L'automate est , avec , et la fonction de transition donnée par la table : Chaque fois que l'on change d'état, la parité du nombre de change.
Extensions des automates finis (dont epsilon transitions)
Il existe plusieurs généralisation des automates finis, selon la nature des étiquettes que l'on autorise sur les transitions. Un automate asynchrone est un automate où l'étiquette d'une transition peut être le mot vide. Une telle transition est appelée une -transition ou transition spontanéeTerminologie de ., et on parle parfois d'automate à -transition. D'autres généralisations autorisent, comme étiquettes, des mots composés de plusieurs lettres. Enfin, une généralisation encore plus large permet comme étiquettes des langages rationnels, représentés par des expressions régulières. Toutes ces extensions n'augmentent pas la puissance des automates finis : un langage reconnu par une quelconque de ces extensions est reconnaissable par un automate fini, et même par un automate fini déterministe.
thumb|Fig. 6 : Automate asynchrone reconnaissant . thumb|Fig. 7 : Automate synchronisé reconnaissant . Un automate asynchrone est un automate fini autorisé à posséder des transitions étiquetées par le mot vide, appelées des -transitions. L'automate de la figure 6 est asynchrone.
L'élimination des -transitions se fait par un algorithme de fermeture transitive comme suit : pour chaque chemin d'un état à un état formé de -transitions, et pour chaque transition de à un état portant une lettre , ajouter une transition de à d'étiquette ; pour chaque chemin d'un état à un état terminal formé de -transitions, ajouter à l'ensemble des états terminaux ; supprimer les -transitions. Dans l'exemple de la figure 6, on ajoute la transition dans la première étape, et on déclare que est état final dans la deuxième étape. On obtient l'automate de la figure 7.
Opérations sur les automates Déterminisation d'un automate fini
Il est toujours possible, à partir d'un automate fini non déterministe , de construire un automate fini déterministe reconnaissant le même langage :
thumb|Fig. 4 : Automate déterminisé des mots se terminant par . thumb|Fig. 5 : Automate déterminisé et émondé.
La méthode de construction est appelée la construction par sous-ensembles en français, et en anglais.
Soit un automate fini sur un alphabet .
On construit l'automate comme suit :