Déterminisation d’un AFN

Nous allons voir comment transformer un automate non déterministe en automate déterministe, ce qui prouvera que la puissance de calcul des automates non déterministes et celle des automates déterministes sont équivalentes.

Idée de base

Prenons un automate non déterministe (Q_N ; Σ_N ; δ_N ; q₀ ; F_N) sans ε-transitions. Nous construisons un automate déterministe (Q_D ; Σ_D ; δ_D ; p₀ ; F_D) de la façon suivante :

Q_D ⊆ 2^Q_N
Σ_D = Σ_N
p₀ = {q₀}
F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Nous définissons la fonction de transition δ_D ainsi :

$\forall Q \in Q_{D}, a \in Σ_{D} : δ_{D} (Q, a) = ⋃_{q \in Q} δ_{N} (q, a)$

Que signifie cela ? Un automate non déterministe peut se trouver dans plusieurs états à la fois ; nous pouvons donc par exemple arriver à une situation où notre automate non déterministe est dans les états {q₀ ; q₁}. En lisant le symbole suivant, par exemple 1, nous pouvons arriver à l’ensemble d’états {q₀ ; q₂ ; q₃}. Dans la version déterministe du même automate, cela se traduit ainsi : nous créons deux états, nous les nommons {q₀ ; q₁} et {q₀ ; q₂ ; q₃}, et nous introduisons entre eux une transition pour le symbole 1. Formellement, nous passons donc d’un état à l’autre, mais grâce aux noms, nous saurons que dans l’automate non déterministe, nous nous serions retrouvés respectivement dans deux et dans trois états.

Exemple

Prenons cet automate non déterministe :

Pour construire l’automate déterministe, nous devons avant tout construire une nouvelle fonction de transition. Un tableau va nous y aider : nous y notons toutes les transitions. Au début, le tableau ressemble à ceci :

$\begin{array}{ccc} état / symbole & 0 & 1 \\ {q_{0}} \end{array}$

Dans la colonne de gauche, nous aurons à la fin de l’algorithme tous les états de l’automate déterministe. Le tableau rempli définira ensuite la fonction de transition. Nous notons maintenant dans le tableau les états que nous atteignons si nous sommes dans l’état {q₀} et que les symboles en entrée sont 0 et 1.

$\begin{array}{ccc} état / symbole & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}; q_{2}} \end{array}$

De l’état q₀, pour le symbole 0, une transition ne mène qu’à l’état q₁, alors que pour le symbole 1, des transitions mènent aux états q₁ et q₂. Nous ajoutons maintenant au tableau deux nouveaux états : {q₁} et {q₁ ; q₂}. Pourquoi ? Dès que nous inscrivons dans le tableau un ensemble d’états qui ne figure pas encore dans la colonne de gauche, nous ajoutons cet ensemble d’états à cette colonne.

$\begin{array}{ccc} état / symbole & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}; q_{2}} \\ {q_{1}} \\ {q_{1}; q_{2}} \end{array}$

et nous remplissons de nouveau. Pour l’état {q₁ ; q₂}, n’oublions pas de vérifier les deux états, c’est-à-dire de prendre la réunion de ce que nous atteignons depuis q₁ et de ce que nous atteignons depuis q₂.

Nous avons obtenu plusieurs nouveaux états, que nous devons ajouter au tableau :

…et nous complétons de nouveau les transitions :

$\begin{array}{ccc} état / symbole & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}; q_{2}} \\ {q_{1}} & {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{3}} \\ {q_{1}; q_{2}} & {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{3}} \\ {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{1}; q_{3}} & {q_{0}; q_{1}; q_{2}; q_{3}} \\ {q_{0}; q_{3}} & {q_{1}} & {q_{1}; q_{2}} \end{array}$

Les états {q₀ ; q₁ ; q₃}, {q₁} et {q₁ ; q₂} figurent déjà dans le tableau, donc nous n’ajoutons que l’état {q₀ ; q₁ ; q₂ ; q₃}.

Nous n’avons ajouté aucun nouvel état, donc le tableau est complet. Il ne reste plus qu’à dessiner le diagramme. Les états de l’automate déterministe sont dans la première colonne, les transitions pour les symboles 0 et 1 dans les suivantes. Tout état qui contient un état final de l’automate d’origine sera aussi un état final dans cet automate. C’est-à-dire que tout état contenant q₃ sera un état final. L’automate ressemblera à ceci :

Nous pouvons vérifier que l’automate fonctionne bien. Essayons d’accepter le mot 11001. Dans l’automate déterministe, nous suivons le chemin

$q_{0} \to^{1} q_{1}; q_{2} \to^{1} q_{0}; q_{3} \to^{0} q_{1} \to^{0} q_{0}; q_{1}; q_{3} \to^{1} q_{0}; q_{1}; q_{2}; q_{3}$

et l’automate accepterait le mot, car le dernier état {q₀ ; q₁ ; q₂ ; q₃} est final. Dans l’automate non déterministe, lors de la simulation, nous arriverions aux mêmes états : nous commencerions dans l’état q₀ et, pour le symbole 1, nous arriverions aux états {q₁ ; q₂}. Le symbole 1 suivant nous mènerait aux états {q₀ ; q₃}, etc. pour les états suivants. Finalement, nous nous retrouverions dans tous les états {q₀ ; q₁ ; q₂ ; q₃} et l’automate accepterait le mot.

Sources

Chapitres: Automate fini, Automate complet, Automate fini non déterministe, Simulation d’un AFN, Déterminisation d’un AFN

« Précédent: Simulation d’un AFN

Suivant: Minimisation des automates »