Voir la source de Automate fini déterministe

{{Article général|Automate fini|Automate fini non déterministe|Théorie des automates}}
{{Voir homonymes|AFD}}

Un  '''automate fini déterministe''', parfois abrégé en '''AFD'''  (en anglais {{lang|en|''deterministic finite automaton''}}, 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 [[langage rationnel|langages rationnels]], appelés aussi langages réguliers ou langages reconnaissables.

== Langages formels ==
Un '''[[alphabet]]''' est, dans ce contexte, tout ensemble <math>\Sigma</math> fini, non vide.
Les éléments de <math>\Sigma </math> sont appelés '''lettres'''.

Un '''[[mot (mathématiques)|mot]]''' est une suite finie d'éléments de <math>\Sigma</math>; 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 <math>\varepsilon</math>, est l'unique mot de longueur zéro, composé d'aucune lettre. L'ensemble des mots sur <math>\Sigma</math> est noté <math>\Sigma^{*}</math>.

La '''concaténation''' de deux mots, notée <math>\cdot</math> ou plus simplement par juxtaposition, est définie pour deux mots <math>u = a_{1}\cdots a_{n}</math> et <math>v = b_{1}\cdots b_{n}</math>par <math>uv = a_{1}\cdots a_{n}b_{1} \cdots b_{n}</math>. On a <math>u\varepsilon = \varepsilon u =u</math>, la concaténation est ''associative'' : <math>u(vw) = (uv)w</math>, par conséquent <math>(\Sigma^{*}, \cdot)</math> est un '''[[monoïde]]'''.

== Automate fini et automate fini déterministe ==
Un '''automate fini''' est un quintuplet <math>\mathcal{A}=\langle\Sigma, Q, R, I, F\rangle</math>, où :

*<math>\Sigma</math> est un alphabet,
*<math>Q</math> est un [[ensemble fini]], appelé ensemble des ''états'',
*<math>R</math> est une partie de <math>Q \times \Sigma \times Q</math> appelée ensemble des ''transitions,'' 
*<math>I</math> est une partie de <math>Q</math> appelée ensemble des ''états initiaux'',
*<math>F</math> est une partie de <math>Q</math> appelée ensemble des états ''finaux.''

Un automate est '''déterministe''' si, d'une part, il a un et un seul état initial et si, d'autre part, la relation <math>R</math> est fonctionnelle au sens suivant :
:si <math>(p,a,q)\in R</math>  et  <math>(p,a,q')\in R</math>, alors <math> q=q'</math>.
S'il en est ainsi, on définit une fonction, appelée '''fonction de transition''' et notée traditionnellement <math>\delta</math>, par :
: <math>\delta(p,a)=q</math> si <math>(p,a,q)\in R</math>.
C'est une [[fonction partielle]] ; son [[Ensemble de définition|domaine de définition]] est l'ensemble des couples <math>(p,a)\in Q \times \Sigma</math> tel qu'il existe <math>q\in Q</math> avec <math>(p,a,q)\in R</math>. 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 <math>\mathcal{A}=\langle\Sigma, Q, \delta, q_0, F\rangle</math>, où :

*<math>\Sigma</math> est un alphabet,
*<math>Q</math> est un ensemble fini, appelé ensemble d'états,
*<math>\delta</math> est une fonction (partielle) de <math>Q \times \Sigma </math> dans <math>Q</math> appelée fonction de transitions, 
*<math>q_0</math> est un élément de <math>Q</math> appelé état initial,
*<math>F</math> est une partie de <math>Q</math> appelée ensemble des états finaux.
La fonction de transition <math>\delta</math> est étendue en une application (partielle) <math>Q\times \Sigma^* \to Q</math> en posant
* <math>\delta(q,\varepsilon)=q</math> pour tout état <math>q</math>. Ici <math>\varepsilon</math> dénote le mot vide.
* <math>\delta(q,wa)=\delta(\delta(q,w),a)</math> pour tout état <math>q</math>, tout mot <math>w</math> et toute lettre <math>a</math>.

On rencontre — notamment dans la littérature francophone — une notation élégante introduite pas [[Samuel Eilenberg]] dans son traité<ref>{{harvsp|Eilenberg|1974|p=}}.</ref> : la fonction de transition est notée par un simple point <math>\cdot</math>. Ainsi, au lieu d'écrire <math>\delta(q,w)</math>, on écrit <math>q \cdot w</math>. On a alors les formules :
* <math>q \cdot \varepsilon=q</math>;
* <math>q \cdot wa=(q\cdot w)\cdot a</math>.
Plus généralement, on a la formule
* <math>q \cdot uv=(q\cdot u)\cdot v</math> 
pour des mots <math>u</math> et <math>v</math> qui se démontre traditionnellement par récurrence sur la longueur du mont <math>v</math>; le cas où <math>v</math> est le mot vide ou est une lettre est vérifié par les formules précédent, et plus généralement, si <math>v=za</math> pour une lettre <math>a</math>, on a
* <math>q \cdot uv=q\cdot uza=(q\cdot uz)\cdot a=((q\cdot u)\cdot z)\cdot a=(q\cdot u) \cdot za=(q\cdot u) \cdot v</math>.
Algébriquement, la dernière formule exprime que le monoïde libre <math>\Sigma^*</math> ''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 [[théorie des graphes|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 <math>(p,a,q)\in R</math> est souvent écrite sous la forme <math> p\overset a \longrightarrow q</math>, empruntée à la représentation graphique. Un '''chemin''' est une suite de flèches consécutives, notée 
:<math>q_0\xrightarrow{a_1} q_1\xrightarrow{a_2} q_2\rightarrow \cdots \xrightarrow{a_n} q_n</math>. 
Sa longueur est le nombre <math>n</math> de ses transitions, son '''étiquette''' (ou trace) est le mot <math>a_1a_2\cdots a_n</math> formé des étiquettes de ses arcs.

On dit qu'un chemin est '''réussi''' lorsque <math>q_0 \in I</math> et <math>q_k \in F</math>. 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 <math>w</math> et pour un état <math>q</math>, au plus un chemin partant de <math>q</math> et d'étiquette <math>w</math>; s'il existe, ce chemin a pour sommet d'arrivée <math>\delta(q,w)</math>. Dire qu'un mot  <math>w</math> est ''reconnu'' s'exprime donc par le fait que <math>\delta(q_0,w)</math> est un état final lorsque <math>q_0</math> est l'état initial. En d'autres termes, le langage accepté ou reconnu par l’automate <math>\mathcal{A}</math> est
: <math>L(\mathcal{A})=\{w\in \Sigma^* \mid \delta(q_0,w)\isin F\}</math>.
Avec la notation par point, cette expression s'écrit
:  <math>L(\mathcal{A})=\{w\in \Sigma^* \mid q_0 \cdot w \isin F\}</math>.
Si on utilise la notation par point, on omet le symbole <math>\delta</math> dans la définition de l’automate.

== Exemple ==
[[File:Automate_reconnaissant_les_mots_commencant_par_ab.png|thumb|upright=1.2|Automate fini reconnaissant les mots commençant par ''ab''.]]
{| class="wikitable floatleft" style="width:100px;text-align:center" 
|+ 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 <math>q\in Q</math> est dit :
* '''accessible''' s'il existe un chemin partant d'un état initial et allant jusqu'à <math>q</math> ;
* '''coaccessible''' s'il existe un chemin partant de l'état <math>q</math> 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 <math>p</math> et toute lettre <math>a</math>, il existe un état <math>q</math> tel que <math>p\xrightarrow a q</math>. 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) <math>\mathcal{A}=\langle\Sigma, Q, \delta, q_0, F\rangle</math>, 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 <math>|Q|\times|\Sigma|</math> 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 <math>s</math> (souvent appelé « état puits », {{Citation étrangère|langue=en|sink state}} en anglais) forcément non final. La fonction de transition <math>\delta</math> est étendu en <math>\Delta</math> posant 
** <math>\Delta(q,a)=s</math> si <math>\delta(q,a)</math> est indéfinie;
** <math>\Delta(s,a)=s</math> pour toute lettre <math>a</math>.

=== 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 <math>\mathcal{A}=\langle\Sigma, Q, q_0, F\rangle</math> un automate fini déterministe et complet et soit <math>L=L(\mathcal{A})</math> le langage reconnu par <math>\mathcal{A}</math>. Le langage complémentaire <math>\bar L =\Sigma^*\setminus L</math> est reconnu  par le même automate, où on a échangé les états terminaux et non terminaux, soit par l'automate <math>\bar\mathcal{A}=\langle\Sigma, Q, q_0, Q\setminus F\rangle</math>.
;Produit direct d'automates 
Soient <math>\mathcal{A}=\langle\Sigma, Q, q_0, F\rangle</math> et Soit <math>\mathcal{B}=\langle\Sigma, P,  p_0, G\rangle</math> deux automates finis déterministes complets, reconnaissant des langages notées respectivement L et M. Le ''produit direct'' des deux automates est l’automate
:<math>\mathcal{C}=\mathcal{A}\times \mathcal{B}=\langle\Sigma, Q\times P, (q_0,p_0), H\rangle</math>
avec la fonction de transition définie par
:<math>(q,p)\cdot a=(q\cdot a, p\cdot a)</math>.
Cette fonction s'étend aux mots et on a
:<math>(q,p)\cdot w=(q\cdot w, p\cdot w)</math>
et <math>H=F\times G</math>. Comme 
:<math>(q_0,p_0)\cdot w\in H \iff q_0\cdot w\in F, p_0\cdot w\in G</math>
le langage reconnu par <math>\mathcal{C}</math> est l’intersection des langages <math>L</math> et <math>M</math>. C'est pourquoi on rencontre aussi la notation <math>\mathcal{A}\cap \mathcal{B}</math> à la place <math>\mathcal{A}\times \mathcal{B}</math>
; 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 <math>H</math> choisi, l'automate <math>\mathcal{C}</math> reconnait la réunion <math>L\cup M</math> ou <math>L\cap M</math>. Le langage réunion <math>L\cup M</math> est reconnu pour <math>H=F\times P\cup Q\times G</math>, le langage <math>L\setminus M = L\cap (A^*\setminus M)</math>, complément de <math>M</math> dans <math>L</math> est reconnu avec  <math>H=F\times (P\setminus G)</math>.
;Inclusion et équivalence
L'inclusion <math>L\subset M</math> est donc facilement testable : il suffit de tester si <math>L\setminus M</math> est vide. De même, l'équivalence des automates, donc la question si <math>L</math> et <math>M</math> 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 <math>\kappa(L)</math> avec [[Janusz Brzozowski|Brzozowski]]<ref>
{{chapitre
|auteur=Janusz Brzozowski 
|titre=Unrestricted State Complexity of Binary Operations on Regular Languages 
|titre ouvrage = Descriptional Complexity of Formal Systems
|année = 2016
|collection = Lecture Notes in Computer Science|numéro dans collection = 9777
|passage = 60-72|arxiv=1602.01387v3}} — La version de [[arXiv]] contient des corrections mineures.</ref>. 

La ''complexité d'une opération binaire'' <math>\odot</math> sur des langages ''L'' et ''M'' est  notée <math>\kappa(L\odot M)</math>. C'est une fonction de  <math>\kappa(L)</math>  et de <math> \kappa(M)</math>. Les opérations booléennes et leurs composées à considérer sont notamment 
*  complémentation <math>\overline L</math>
* union <math>L\cup M</math>
* intersection <math>L\cap M</math>
* différence symétrique <math>L\oplus M</math>
* différence <math>L \setminus M</math>
On a par exemple <math>\kappa(\overline L)= \kappa(L)</math> 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 :
:<math>\kappa(\overline L\cup M) = \kappa(\overline{\bar L\cup M}) = \kappa(L\cap \overline M) = \kappa(L\setminus M)</math>.

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é  <math>\kappa(L)=m</math>  et <math> \kappa(M)=n</math> 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 <math>(m+1)(n+1)</math>  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 <math>(m+1)n</math>.
* La complexité de l’intersection est au plus <math>mn</math>.
* La complexité du produit ''LM'' est au plus <math>m2^n-2^{n-1}</math>.
Toutes ces bornes peuvent être atteintes. Pour illustrer l'importance de l'alphabet, on considère les langages <math>L=a^*</math> et <math>M=b^*</math> formés des mots sur une seule lettre <math>a</math> respectivement <math>b</math>, avec <math>a\ne b</math>. Chacun des deux langages est reconnu par un automate à un seul état. La réunion <math>a^*\cup b^*</math> est de complexité 4=(1+1)(1+1). Si les langages <math>L=a^*</math> et <math>M=b^*</math> sont considérés comme étant l'un et l'autre sur l'alphabet <math>\{a,b\}</math>, leurs automates minimaux ont chacun  2 états et l'automate de leur union a bien <math>4=2\cdot 2</math> é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 [[automate fini non déterministe|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 construction<ref>Ces constructions se trouvent dans le livre de {{Ouvrage
 |auteur1=John E. Hopcroft
 |auteur2=Jeffrey D. Ullman
 |titre=Formal languages and their relation to automata
 |éditeur=Addison-Wesley
 |année=1969
 |isbn=
}}.</ref>.
;Automate pour le produit
Soient <math>\mathcal{A}=\langle\Sigma, Q, q_0, F\rangle</math> et <math>\mathcal{B}=\langle\Sigma, P, p_0, T\rangle</math> deux automates finis déterministes reconnaissant des langages <math>L</math> et <math>M</math> respectivement. Un automate non déterministe <math>\mathcal{C}</math> reconnaissant le langage produit <math>LM</math> est défini comme suit : l'ensemble de ses états est <math>Q\cup P</math> (on suppose ces deux [[ensembles disjoints]]), l'état initial est <math>q_0</math> (l'état initial de <math>\mathcal{A}</math>, l'ensemble des états terminaux est <math>T</math> (états terminaux de <math>\mathcal{B}</math>). Les transitions sont celles définies par les fonctions de transitions de <math>\mathcal{A}</math> et <math>\mathcal{B}</math>, avec en plus des transitions <math>(q,a,p_0)</math> pour toute paire <math>(q,a)</math> formée d'un état de <math>\mathcal{A}</math> et d'une lettre telle que <math>q\cdot a\in F</math>. Ainsi, chaque fois que l’automate <math>\mathcal{A}</math> arrive dans un état qui peut déboucher sur in de ses états finaux, la transition ajoutée permet aussi d'anticiper le début d'un calcul dans l’automate <math>\mathcal{B}</math>.
;Automate pour l'étoile
La construction est analogue. Partant d'un automate <math>\mathcal{A}=\langle\Sigma, Q, q_0, F\rangle</math>, on construit un automate
:<math>\mathcal{B}=\langle\Sigma, Q\cup p_0, p_0, F\cup p_0\rangle</math>,
où <math>p_0</math> est un nouvel état qui est son état initial et aussi un état final. La fonction de transition de <math>\mathcal{A}</math> est étendue à <math>p_0</math> par
:<math>p_0\cdot a=q_0\cdot a</math> pour toute lettre <math>a</math>;
de plus, on ajoute les transitions <math>(q,a,q_0)</math> pour quand <math>q\cdot a\in F</math>, et la transition <math>(p_0,a,q_0)</math> si <math>q_0\cdot a\in F</math>.

== Automate minimal ==
Deux automates finis déterministes sont ''équivalents'' s'ils reconnaissent le même langage. C'est un résultat remarquable de la théorie qu'il existe, pour tout automate fini, un seul automate fini déterministe minimal (c'est-à-dire ayant un nombre minimal d'état) qui est équivalent à l'automate donné. De plus, cet automate, appelé automate minimal, possède une description algébrique simple et élégante. Par ailleurs, l'automate se calcule efficacement par l'[[algorithme de Moore de minimisation d'un automate fini|algorithme de Moore]] ou l'[[minimisation d'un automate fini déterministe|algorithme de Hopcroft]]. L'unicité de l'automate ayant un nombre minimal d'état n'est plus vraie pour les automates non déterministes.

=== Définition algébrique ===
Soit <math>L</math> un langage formel sur un alphabet fini <math>A</math>. Pour tout mot <math>x</math>, le ''[[langage formel#Opérations sur les langages formels|quotient gauche]]'' ou ''[[langage formel#Opérations sur les langages formels|résiduel]]'' de <math>L</math> par <math>x</math> de <math>L</math> par <math>x</math>, est l'ensemble noté <math>x^{-1}L</math> et défini par
:<math>x^{-1}L=\{z\in A^*\mid xz\in L\}</math>.
On a 
:<math>\varepsilon^{-1}L=L</math> et <math>(xy)^{-1}L=y^{-1}(x^{-1}L)</math>
pour tout <math>x,y</math>.

L''''automate fini déterministe minimal''' reconnaissant <math>L</math>, aussi appelé '''automate des quotients'''<ref>{{harvsp|id=Sakarovitch|texte=Sakarovitch 2003|p=}}.</ref> et noté parfois <math>\mathcal{A}(L)</math>, est défini comme suit :
* son ensemble d'états est l'ensemble <math>\{x^{-1}L \mid x\in A^*\}</math> des quotients gauche de <math>L</math> ;
* son état initial est <math>i_L=\varepsilon^{-1}L=L</math> ;
* les états terminaux  <math>T_L</math> sont les états contenant le mot vide ;
* la fonction de transition est définie, pour tout état <math>M</math> et <math>a\in A</math> par <math>M\cdot a= a^{-1}M</math>.
On a <math>M\cdot x= x^{-1}M</math> pour tout mot <math>x</math>. Il en résulte que
:<math>i_L\cdot x\in T_L \iff x^{-1}L\in T_L \iff \varepsilon\in x^{-1}L \iff x\in L</math>.
Ceci prouve que l'automate <math>\mathcal{A}(L)</math>, reconnaît bien le langage <math>L</math>.

=== Relation de Myhill-Nerode et résiduels ===
On définit une relation <math>\sim_L</math>  sur les mots, appelée ''relation de Myhill-Nerode'', par la règle : <math>x \sim_L y</math> si et seulement si <math>x^{-1}L=y^{-1}L</math>. inséparables. La relation <math>\sim_L</math> est une [[relation d'équivalence]] sur les mots, et donc partitionne l'ensemble de tous les mots en [[relation d'équivalence#Classe d'équivalence|classes d'équivalences]]. Les classes de l'équivalence de Myhill-Nerode sont donc en [[bijection]] avec les résiduels de <math>L</math>. Il en résulte qu'un langage est rationnel si et seulement si l'ensemble de ses résiduels est fini<ref>C'est sous cette forme que le théorème est énoncé dans le traité d'Eilenberg ({{harvsp|Eilenberg|1974}}, Théorème 8.1 (The Quotient Criterion), page 55.)</ref>.

=== Minimalité ===
La minimalité de l'automate <math>\mathcal{A}(L)</math> peut être établie de plusieurs façons équivalentes. 
Soit <math>\mathcal{A}=(Q,i,T)</math> un automate déterministe complet accessible reconnaissant le langage <math>L</math>. Pour tout état <math>q</math>, on note <math>L_q=\{w\in A^*\mid q\cdot w\in T\}</math>. C'est donc l'ensemble des mots w qui étiquettent un chemin de q vers un état final. Soit <math>x</math> un mot tel que <math>i\cdot x=q</math>. Un tel mot existe parce que tout état de l'automate est accessible. On a alors
<math>L_q=x^{-1}L</math>
puisque 
:<math>w\in L_q\iff q\cdot w\in T \iff i\cdot x\cdot w\in T =\iff i\cdot xw\in T \iff xw\in L \iff w\in x^{-1}L</math>.
En d'autres termes, les états de tout automate <math>\mathcal{A}</math> déterministe complet accessible reconnaissant le langage <math>L</math> s'identifient aux quotients gauches, deux états qui sont équivalents dans l'automate <math>\mathcal{A}</math> sont les mêmes dans l'automate minimal.

=== Morphisme d'automates ===
Selon le degré de généralité recherché, il y a des variations dans la définition d'un morphisme d'automate. Soient <math>\mathcal{A}=(Q,i, T)</math> et <math>\mathcal{A'}=(Q',i', T')</math> deux automates finis déterministes accessibles et complets. Un '''morphisme''' de <math>\mathcal{A}</math> dans <math>\mathcal{A'}</math> est une application <math>f:Q\to Q'</math> telle que :
* <math>f(i)=i'</math>
* <math>f(q\cdot a)=f(q)\cdot a</math>, pour tout lettre <math>a</math>,
* <math>f(T)\subset T'</math>.

La deuxième propriété s'étend aux mots par récurrence : on a <math>f(q\cdot x)=f(q)\cdot x</math> pour tout mot <math>x</math>. Le langage <math>L(\mathcal{A})</math> reconnu par <math>\mathcal{A}</math> est contenu dans le langage <math>L(\mathcal{A'})</math> reconnu par <math>\mathcal{A'}</math> puisque pour un mot <math>x</math> de <math>L(\mathcal{A})</math>, on a <math>i\cdot x \in T</math>, et <math>f(i\cdot x)=f(i)\cdot x=i'\cdot x\in T'</math>. 

Si de plus <math>f(T)=T'</math>, on dit que le morphisme est ''surjectif'', et  alors <math>L(\mathcal{A})=L(\mathcal{A'})</math> ; en effet, soit <math>x\in L(\mathcal{A'})</math>, et soit <math>t'\in T'</math> l'état terminal tel que <math>i'\cdot x= t'</math>. Soit <math>t\in Q</math> l'état tel que  <math>i\cdot x= t</math>. Alors <math>f(t)=t'</math>, et donc <math>t\in T</math>.

Soit maintenant <math>\mathcal{A}=(Q,i, T)</math> un automate reconnaissant un langage <math>L=L(\mathcal{A})</math> et soit <math>\mathcal{A}(L)</math> l'automate minimal de <math>L</math> défini ci-dessus. On définit un morphisme d'automate
:<math>f  : \mathcal{A}\to \mathcal{A}(L)</math>
comme suit : pour tout état <math>q\in Q</math>, soit <math>w</math> un mot tel que <math>i\cdot w=q</math>. Alors 
:<math>f(q)=w^{-1}L</math>.
La définition est indépendante du mot <math>w</math> choisi, et c'est bien un morphisme [[Surjection|surjectif]]. 

Il résulte de cette construction que
* l'automate minimal, image homomorphe de tout automate équivalent, a bien le plus petit nombre possible d'états;
* l'automate minimal est unique à un renommage des états près puis qu'étant donné deux tels automates, il existe un morphisme de l’un sur l'autre, donc un isomorphisme entre les deux.

Cette propriété remarquable des automates finis déterministes n'est plus vraie pour des automates finis non déterministes.

== Voir aussi ==
* [[Automate fini]]
* [[Automate fini non déterministe]]
* [[Automate fini inambigu]]
* [[Automate à pile]]
* [[Automate d'arbres]]
* [[Théorème de Kleene]]

== Bibliographie ==
;Ouvrages
* {{Langages formels, calculabilité et complexité}}
* {{Ouvrage| id=Sakarovitch| auteur1=Jacques Sakarovitch| titre=Éléments de théorie des automates| éditeur=Vuibert| année=2003| pages totales=816| isbn=978-2-7117-4807-5}}{{commentaire biblio|Traduction anglaise avec corrections : ''Elements of Automata Theory'', Cambridge University Press 2009, {{ISBN|9780521844253}}}}
* {{Ouvrage| prénom1=Patrice| nom1=Séébold| titre=Théorie des automates| sous-titre=Méthodes et exercices corrigés| éditeur=Vuibert| année=1999| pages totales=198| pages=198| isbn=978-2-7117-8630-5}}
* {{chapitre|auteur= Jean-Éric Pin |titre chapitre = Automates finis 
|auteurs ouvrage =Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs)
|titre ouvrage =Encyclopédie de l'informatique et des systèmes d'information
|éditeur=Vuibert|lieu=Paris|année=2006|pages totales=xxxv+1941 |passage=966-976|isbn=978-2-7117-4846-4|id=EISI}}.
* {{Introduction to Automata Theory, Languages, and Computation}}
* {{Ouvrage
| auteur1=Samuel Eilenberg
| titre=Automata, Languages and Machines, Vol. A
| éditeur=Academic Press
| année=1974
| isbn=978-0-12-234001-7
}}
;Cours
* Luc Maranget, [http://pauillac.inria.fr/~maranget/X/421/poly/automate.html « Chapitre 7 Les automates »], Notes de cours à l’École polytechnique.
* Jean-Marc Fédou, [http://www.i3s.unice.fr/~fedou/wwwUnice/CoursOFI_files/OFI8.pdf « 8. Automates finis »], Université de Nice.
* Sylvain Lombardy, [http://igm.univ-mlv.fr/~lombardy/ens/cours-ir09.pdf « Automates, Notions de base »],  Université Marne-la-Vallée.
* Élise Bonzon, [http://www.mi.parisdescartes.fr/~bonzon/Cours/Langages/03_automates_finis.pdf « Théorie de Langages - Automates finis »], Université Paris Descartes.
* Benjamin Monmège et Sylvain Schmitz, [http://www.lsv.ens-cachan.fr/~schmitz/teach/2012_agreg/notes-r62.pdf « Automates et langages »], Préparation à l’agrégation de mathématiques 2011–2012, LSV, ENS Cachan & CNRS.
* Abdelmajid Dergham<ref>{{Lien web|langue=francais|titre=computer sciences - Compilation (SMI S5)|url=http://www.comp.sci.sitew.com/Compilation_SMI_S5_.C.htm#Compilation_SMI_S5_.C|site=SiteW.com|consulté le=2017-11-16}}</ref>,Université Mohammed Premier Oujda.

== Notes et références ==
{{Références}}

{{Palette Automates finis et langages réguliers}}
{{portail|informatique|informatique théorique}}

{{DEFAULTSORT:Automate fini déterministe}}
[[Catégorie:Théorie des automates]]
[[Catégorie:Calculabilité]]
[[Catégorie:Méthode formelle]]
[[Catégorie:Automates finis et langages réguliers]]