Un automate fini déterministe, parfois abrégé en AFD (en anglais , abrégé en DFA) est un automate fini dont les transitions à partir de chaque état sont déterminées de façon unique par le symbole d'entrée. Un tel automate se distingue ainsi d'un automate fini non déterministe, où au contraire plusieurs possibilités de transitions peuvent exister simultanément pour un état et un symbole d'entrée donné.
Les automates finis déterministes ont plusieurs aspects avantageux : simplicité de leur définition, facilité de manipulation, aisance de la programmation informatique, élégance des propriétés mathématiques. Leur inconvénient majeur est la taille, mesurée en nombre d'états, qui peut dans certains cas être exponentielle par rapport à leur contrepartie non déterministe. Les deux classes d'automates finis, les automates finis déterministes et non déterministes, ont la même puissance d'expression : elles reconnaissent la même famille de langages, à savoir les langages rationnels, appelés aussi langages réguliers ou langages reconnaissables.
Langages formels Un alphabet est, dans ce contexte, tout ensemble fini, non vide. Les éléments de sont appelés lettres.
Un mot est une suite finie d'éléments de ; la longueur d'un mot est le nombre d'éléments qui le composent. Un mot est noté par la juxtaposition de ses lettres. Ainsi, on écrit « oui » plutôt que « (o,u,i) ». Le mot vide, noté souvent , est l'unique mot de longueur zéro, composé d'aucune lettre. L'ensemble des mots sur est noté .
La concaténation de deux mots, notée ou plus simplement par juxtaposition, est définie pour deux mots et par . On a , la concaténation est associative : , par conséquent est un monoïde.
Automate fini et automate fini déterministe Un automate fini est un quintuplet , où :
est un alphabet, est un ensemble fini, appelé ensemble des états, est une partie de appelée ensemble des transitions, est une partie de appelée ensemble des états initiaux, est une partie de appelée ensemble des états finaux.
Un automate est déterministe si, d'une part, il a au plus un état initial et si, d'autre part, la relation est fonctionnelle au sens suivant : si et , alors . S'il en est ainsi, on définit une fonction, appelée fonction de transition et notée traditionnellement , par : si . C'est une fonction partielle ; son domaine de définition est l'ensemble des couples tel qu'il existe avec . Dans les manuels, on rencontre aussi la définition suivante d'un automate fini déterministe qui est directe et n’est pas dérivée d'une définition plus générale :
Un automate fini déterministe est un quintuplet , où :
est un alphabet, est un ensemble fini, appelé ensemble d'états, est une fonction (partielle) de dans appelée fonction de transitions, est un élément de appelé état initial, est une partie de appelée ensemble des états finaux. 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 .
On rencontre — notamment dans la littérature francophone — une notation élégante introduite pas Samuel Eilenberg dans son traité. : la fonction de transition est notée par un simple point . Ainsi, au lieu d'écrire , on écrit . On a alors les formules : ; . Plus généralement, on a la formule
pour des mots et qui se démontre traditionnellement par récurrence sur la longueur du mont ; le cas où est le mot vide ou est une lettre est vérifié par les formules précédent, et plus généralement, si pour une lettre , on a . Algébriquement, la dernière formule exprime que le monoïde libre opère à droite sur l'ensemble d'états de l’automate.
Représentation graphique Un automate fini, déterministe ou non, est représenté par un graphe dont les sommets sont les états, et les arcs sont les transitions. C'est donc un graphe orienté, étiqueté aux arcs par des lettres de l’alphabet. Une symbolique spéciale distingue les états initiaux et terminaux : un état initial est marqué par une flèche entrante, un état terminal par une flèche sortante ou par un double cercle.
Une transition est souvent écrite sous la forme , empruntée à la représentation graphique. Un chemin est une suite de flèches consécutives, notée . Sa longueur est le nombre de ses transitions, son étiquette (ou trace) est le mot formé des étiquettes de ses arcs.
On dit qu'un chemin est réussi lorsque et . Un mot est reconnu lorsqu'il est l'étiquette d'un chemin réussi. Le langage accepté ou reconnu par l’automate est l’ensemble des mots qu'il reconnaît.
Langage reconnu
Dans le cas d'un automate fini déterministe, il n'y a, pour un mot et pour un état , au plus un chemin partant de et d'étiquette ; s'il existe, ce chemin a pour sommet d'arrivée . Dire qu'un mot est reconnu s'exprime donc par le fait que est un état final lorsque est l'état initial. En d'autres termes, le langage accepté ou reconnu par l’automate est . Avec la notation par point, cette expression s'écrit . Si on utilise la notation par point, on omet le symbole dans la définition de l’automate.
Exemple
+ Table de transitions a b 1 2 - 2 - 3 3 3 3 L'automate ci-contre est composé de trois états; l'état 1 est le seul état initial, distingué par une flèche entrante, l'état 3 est le seul état terminal, distingué par une flèche sortante. C'est un automate déterministe. Il reconnaît les mots, sur deux lettres a et b, qui commencent par ab. La fonction de transition est donnée par sa table de transitions. L'absence de flèche est représentée par un tiret : la présence d'un tiret montre que la fonction de transition est partielle.
Propriétés Accessibilité
Un état est dit : accessible s'il existe un chemin partant d'un état initial et allant jusqu'à ; coaccessible s'il existe un chemin partant de l'état et allant jusqu'à un état final.
Un automate est dit : accessible si tous ses états sont accessibles ; coaccessible si tous ses états sont coaccessibles ; émondé s'il est à la fois accessible et coaccessible.
Une fois l'automate rendu accessible, on peut tester si le langage reconnu est vide ou non : pour qu'il soit vide, il faut et il suffit qu'aucun état final ne soit accessible.
Complétude Un automate est complet s'il possède au moins un état initial et si, pour chaque état et pour chaque lettre, il existe au moins une flèche sortante, c’est-à-dire si, pour tout état et toute lettre , il existe un état tel que . On reconnaît la complétude sur la table de transition d'un automate déterministe par le fait qu'aucune case du tableau n'est vide.
Émondage et complétion Étant donné un automate fini déterministe (les mêmes algorithmes s'appliquent aux automates non déterministes) , les algorithmes de parcours usuels en théorie des graphes permettent d'émonder et de compléter un automate : on détermine les états accessibles par un calcul des descendants de l’état initial, donc par un parcours du graphe à partir du sommet qui est l'état initial; un algorithme linéaire en permet de les calculer. Le graphe de l’automate, et sa fonction de transition, est alors réduit aux sommets accessibles; on détermine ensuite les sommets coaccessibles par un calcul des ascendants des sommets terminaux. Les mêmes algorithmes de parcours permettent de réaliser cette opération en temps linéaire; la complétion d'un automate, s'il est incomplet, se fait par l’adjonction d'un nouvel état, disons (souvent appelé « état puits », en anglais) forcément non final. La fonction de transition est étendu en posant si est indéfinie ; pour toute lettre .
Opérations booléennes Pour ces opérations, on considère un automate déterministe et complet : la fonction de transition sera représentée par un point. Complémentation Soit un automate fini déterministe et complet et soit le langage reconnu par . Le langage complémentaire est reconnu par le même automate, où on a échangé les états terminaux et non terminaux, soit par l'automate . Produit direct d'automates Soient et Soit deux automates finis déterministes complets, reconnaissant des langages notées respectivement L et M. Le produit direct des deux automates est l’automate
avec la fonction de transition définie par . Cette fonction s'étend aux mots et on a
et . Comme
le langage reconnu par est l’intersection des langages et . C'est pourquoi on rencontre aussi la notation à la place Union, intersection, complément relatif On peut modifier la définition du produit direct en choisissant d'autres états terminaux. Ainsi, selon l'ensemble d'états terminaux choisi, l'automate reconnait la réunion ou . Le langage réunion est reconnu pour , le langage , complément de dans est reconnu avec . Inclusion et équivalence L'inclusion est donc facilement testable : il suffit de tester si est vide. De même, l'équivalence des automates, donc la question si et sont égaux, est facile à tester puisqu'elle se ramène à deux inclusions.
Complexité des opérations booléennes La complexité d’un langage rationnel L peut se mesurer de diverses façons ; dans le cadre des automates finis déterministes, il est nature de la définir comme le nombre d’états de l’automate déterministe complet minimal reconnaissant ce langage. Par le théorème de Myhill-Nerode, c'est aussi le nombre de résiduels ou quotients gauches du langage. On note ce nombre avec Brzozowski — La version de arXiv contient des corrections mineures..
La complexité d'une opération binaire sur des langages L et M est notée . C'est une fonction de et de . Les opérations booléennes et leurs composées à considérer sont notamment complémentation union intersection différence symétrique différence On a par exemple puisque les automates minimaux ne diffèrent que par les états terminaux dont les ensembles sont complémentaire. La complexité d’autres opérations peut s’en déduire, par exemple : .
Quand on évalue la complexité des opérations, il faut préciser si les langages sont donnés sur le même alphabet ou non. Soient L et M deux langages rationnels de complexité et respectivement, pas nécessairement sur le même alphabet. Les résultats sont les suivants : La complexité de l’union et de la différence symétrique de L et M est au plus . La complexité de l’union de langages L et M sur le même alphabet est au plus mn. La complexité de la différence est au plus . La complexité de l’intersection est au plus . La complexité du produit LM est au plus . Toutes ces bornes peuvent être atteintes. Pour illustrer l'importance de l'alphabet, on considère les langages et formés des mots sur une seule lettre respectivement , avec . Chacun des deux langages est reconnu par un automate à un seul état. La réunion est de complexité 4=(1+1)(1+1). Si les langages et sont considérés comme étant l'un et l'autre sur l'alphabet , leurs automates minimaux ont chacun 2 états et l'automate de leur union a bien états.
Produit et étoile Les algorithmes pour le calcul de l'automate reconnaissant le produit ou l’étoile d'un langage décrits pour les automates non déterministes sont bien entendu applicables aussi quand on part d'un automate déterministe, mais le résultat est un automate non déterministe, et même avec des ε-transitions. Autant le non déterminisme ne s'élimine que dans une deuxième étape, autant on peut, avec un peu de soin, éviter l'introduction des ε-transitions dont l'élimination ultérieure constitue une phase supplémentaire dans la constructionCes constructions se trouvent dans le livre de .. Automate pour le produit