Conversion AFN vers AFD: Méthode des Sous-ensembles

1. L'Idée Fondamentale : Les États du Déterminisme sont des Ensembles

Le non-déterminisme se manifeste par le "choix". Dans un AFN, en lisant un symbole a depuis un état $q$, nous pouvons aboutir à un ensemble d'états possibles : $\{q_1,q_2,\dots \}$. Un AFD, par définition, ne peut aboutir qu'à un seul état.

Comment résoudre cette ambiguïté ? L'idée est d'une simplicité redoutable : si l'AFN peut se trouver simultanément dans plusieurs états, alors l'AFD équivalent aura un unique état qui représente précisément cet ensemble d'états.

Chaque état du nouvel AFD correspondra donc à un sous-ensemble d'états de l'AFN d'origine.

La vidéo suivante introduit cette idée et décompose la construction du nouvel automate déterministe en ses différents éléments : ses états, son état initial, ses états finaux et ses transitions.

Pour formaliser ce que vous venez de voir : soit un AFN $A_N=(Q_N,\Sigma ,{\delta }_N,I_N,F_N)$. Nous construisons un AFD $A_D=(Q_D,\Sigma ,{\delta }_D,q_{D0},F_D)$ où :

• États $Q_D$ : Les états de l'AFD sont des sous-ensembles d'états de l'AFN. Formellement, $Q_D\subseteq \mathcal{P}(Q_N)$.
• État initial $q_{D0}$ : L'état initial de l'AFD est l'ensemble des états initiaux de l'AFN, soit $q_{D0}=I_N$. (Nous affinerons cela pour les $ϵ$-transitions).
• États finaux $F_D$ : Un état $S\in Q_D$ est un état final de l'AFD si et seulement s'il contient au moins un état final de l'AFN. Formellement, $F_D=\{S\in Q_D\mid S\cap F_N\ne \varnothing \}$.

Il ne nous reste plus qu'à définir la fonction de transition ${\delta }_D$, qui est le cœur de l'algorithme.

2. L'Algorithme de Construction des Sous-Ensembles

La construction de l'AFD se fait de manière itérative. Il serait inefficace de créer d'emblée les $2^{|Q_N|}$ états possibles. Nous ne construirons que les états accessibles depuis l'état initial. La méthode la plus rigoureuse consiste à utiliser une table de transitions pour l'AFD en construction.

La vidéo suivante détaille cette approche tabulaire.

La logique de transition est la suivante : pour un état-ensemble $S$ de l'AFD et un symbole $a\in \Sigma$, l'état-ensemble de destination $S^{\prime }$ est l'union de toutes les destinations possibles depuis chaque état $q\in S$ de l'AFN en lisant $a$.

${\delta }_D(S,a)=S^{\prime }={\bigcup }_{q\in S}{\delta }_N(q,a)$

Si $S^{\prime }=\varnothing$, cela signifie qu'aucune transition n'est possible. Dans l'AFD, cela correspond à une transition vers un état puits (trap state), un état non-final dont toutes les transitions bouclent sur lui-même.

Le document de cours ci-dessous formalise l'ensemble de ce processus dans un pseudo-code rigoureux, que vous devez être capable de comprendre et de reproduire.

3. La Gestion des $ϵ$-Transitions

Jusqu'à présent, nous avons ignoré un détail crucial : les transitions spontanées, ou $ϵ$-transitions. Celles-ci permettent à un automate de changer d'état sans consommer de symbole. Elles doivent être intégrées à notre algorithme.

Pour cela, nous introduisons la notion de clôture-epsilon (ou clôture instantanée), notée $c{l}_{ϵ}(S)$. C'est l'ensemble de tous les états atteignables depuis un ensemble d'états $S$ en ne suivant que des $ϵ$-transitions (y compris les états de $S$ eux-mêmes).

L'algorithme de construction des sous-ensembles est alors modifié comme suit :

1. État initial de l'AFD : L'état initial est la clôture-epsilon de l'ensemble des états initiaux de l'AFN.
   $q_{D0}=c{l}_{ϵ}(I_N)$

2. Fonction de transition de l'AFD : Pour aller de l'état-ensemble $S$ à $S^{\prime }$ avec le symbole $a$, la procédure est :
   a. Calculer l'ensemble des états atteignables depuis $S$ en lisant a (sans $ϵ$-transitions). Appelons cet ensemble $T$. $T={\bigcup }_{q\in S}{\delta }_N(q,a)$.
   b. L'état de destination $S^{\prime }$ est alors la clôture-epsilon de $T$.
   ${\delta }_D(S,a)=S^{\prime }=c{l}_{ϵ}(T)=c{l}_{ϵ}\left({\bigcup }_{q\in S}{\delta }_N(q,a)\right)$

En d'autres termes, à chaque pas de calcul de l'AFD, on effectue une séquence : (zéro ou plus ε-transitions) -> une transition sur un symbole -> (zéro ou plus ε-transitions). C'est le polycopié IF114 – Automates finis et applications qui formalise ce point dans la section 2.1.3 que nous allons maintenant étudier.

L'image ci-dessous illustre un exemple de calcul de clôture-epsilon et de transitions, qui sont les briques de base de l'algorithme complet.

4. Complexité et Limites

La déterminisation est un algorithme puissant, mais il a un coût. Dans le pire des cas, le nombre d'états de l'AFD résultant peut être exponentiel par rapport au nombre d'états de l'AFN de départ. Si l'AFN a $n$ états, l'AFD peut en avoir jusqu'à $2^n$.

C'est un résultat théorique fondamental à connaître. Les notes de révision de l'ENS Paris-Saclay le mentionnent et fournissent même un exemple classique d'automate qui provoque cette explosion d'états (Exemple 1.14 dans le document Notes de révision : Automates et langages). Bien que nous ne l'étudiions pas en détail ici, il est bon de savoir que ces cas existent.

En pratique, cependant, l'algorithme ne construit que les états accessibles, et l'automate résultant est souvent de taille raisonnable. C'est le point soulevé dans la première vidéo (Comprendre la déterminisation..., 09:09) : la construction des seuls états accessibles est en général suffisante et bien plus performante.

Conclusion

Aujourd'hui, nous avons disséqué l'un des algorithmes les plus importants de la théorie des langages. La construction des sous-ensembles n'est pas seulement une procédure mécanique ; c'est la preuve constructive que le non-déterminisme, bien qu'utile pour la conception, n'ajoute aucune puissance de reconnaissance aux automates finis.

Points clés à retenir :

• Principe fondamental : Un état dans l'AFD équivalent représente un ensemble d'états de l'AFN d'origine.
• Algorithme : La construction est itérative et ne génère que les états accessibles depuis l'état initial pour éviter l'explosion combinatoire.
• $ϵ$-Transitions : Leur gestion est cruciale et se fait via le calcul de la clôture-epsilon à deux moments : pour définir l'état initial et après chaque transition sur un symbole.
• Finalité : Un état de l'AFD est final s'il contient au moins un état final de l'AFN.
• Complexité : La taille de l'AFD résultant est au pire exponentielle ($O(2^n)$), mais souvent bien plus petite en pratique.

Dans notre prochaine leçon, nous explorerons une autre manière de décrire les langages réguliers : les expressions régulières. Nous verrons comment elles se connectent aux automates, complétant ainsi le triptyque (AFD, AFN, expressions régulières) des représentations équivalentes des langages réguliers, un théorème central connu sous le nom de théorème de Kleene.