DevUn automate fini non-déterministe (NFA) accepte les mêmes langages qu'un automate déterministe (DFA). Mais pour l'implémentation (analyse lexicale, reconnaissance de motifs), on préfère les DFA. La déterminisation transforme l'un en l'autre.
Méthode des sous-ensembles
Idée : l'état du DFA est un sous-ensemble d'états du NFA. On part de l'état initial, on calcule les transitions sur chaque lettre de l'alphabet, et on étend l'ensemble d'états à mesure qu'on rencontre de nouveaux sous-ensembles atteignables.
Un état du DFA est acceptant si le sous-ensemble correspondant contient au moins un état acceptant du NFA.
Algorithme
- 1. État initial du DFA : $\{q_0\}$ (ou sa ε-clôture si le NFA a des transitions ε)
- 2. Pour chaque état courant $S$ du DFA et chaque lettre $a$ : calculer $T = \bigcup_{q \in S} \delta(q, a)$ (puis ε-clôture si applicable)
- 3. Si $T$ est nouveau, l'ajouter aux états du DFA
- 4. Transition dans le DFA : $S \xrightarrow{a} T$
- 5. Répéter jusqu'à ce qu'aucun nouvel état ne soit créé
Complexité
Le DFA résultant peut contenir jusqu'à $2^{|Q|}$ états (toutes les parties de l'ensemble d'états du NFA). Explosion combinatoire possible, mais en pratique on atteint rarement cette borne.
Une optimisation classique : calculer uniquement les sous-ensembles atteignables depuis l'état initial.
Exemple complet
Prenons un NFA à 3 états $\{q_0, q_1, q_2\}$ sur alphabet $\{a, b\}$, avec $q_0$ initial et $q_2$ acceptant. Transitions : $q_0 \xrightarrow{a} q_0$, $q_0 \xrightarrow{a} q_1$, $q_1 \xrightarrow{b} q_2$.
Déterminisation : état initial DFA = $\{q_0\}$. Sur $a$ : $\{q_0, q_1\}$ (nouvel état). Sur $b$ : $\emptyset$ (piège). Depuis $\{q_0, q_1\}$, sur $a$ on retombe sur $\{q_0, q_1\}$, sur $b$ on obtient $\{q_2\}$ (nouvel état, acceptant).
Le DFA résultant a 4 états : $\{q_0\}, \{q_0, q_1\}, \{q_2\}, \emptyset$. États acceptants : tout sous-ensemble contenant $q_2$.
Cas extrême : explosion exponentielle
Il existe des NFA à $n$ états dont le DFA minimal a exactement $2^n$ états. Un exemple classique : le langage des mots sur $\{a, b\}$ dont la $n$-ième lettre depuis la fin est un $a$.
Un NFA reconnaît ce langage avec $n+1$ états, mais un DFA doit « mémoriser » les $n$ dernières lettres, ce qui exige $2^n$ états. Cette explosion est intrinsèque — pas un artefact de l'algorithme de déterminisation.
Une question ou une suggestion ? Écrivez-nous.