Automate fini non déterministe

L’automate fini présenté dans les chapitres précédents (que nous abrégeons en AF ou AFD) était toujours déterministe : à chaque instant, on savait exactement ce que l’automate allait faire. Nous allons maintenant étudier la notion plus générale d’automate fini non déterministe (que nous abrégeons en AFN), dans lequel plusieurs transitions peuvent partir du même état pour le même symbole.

Exemple

Observe le diagramme de l’automate suivant :

Qu’a-t-il de particulier ? Du nœud q₀ partent deux arcs pour le symbole 0. Si nous essayons donc d’accepter le mot 001, l’automate ne semble pas savoir s’il doit rester dans l’état q₀ ou suivre la transition vers q₁. Un tel automate est non déterministe.

Le déterminisme, dans ce sens, signifie qu’à chaque situation, on sait ce que fait l’automate : il n’y a aucune place pour l’ambiguïté. Un automate déterministe n’a qu’une seule transition pour chaque état et chaque symbole. Le non-déterminisme désigne l’ambiguïté : d’un même état, il peut partir par exemple trois transitions pour le même symbole.

Comment l’automate se décide-t-il donc ? Un automate non déterministe choisit toujours (on dit parfois aussi qu’il « devine ») la transition qui mène à l’acceptation du mot, lorsque c’est possible.

Si nous donnons à l’automate le mot 001, voici les chemins qu’il peut suivre :

$\begin{array}{r} q_{0} \to q_{0} \to q_{0} \to q_{0} \\ q_{0} \to q_{0} \to q_{1} \to q_{2} \end{array}$

auxquels s’ajoutent les chemins où il ne lit pas le mot en entier. Dans le premier, il reste tout le temps dans l’état q₀, ce qu’il a bien le droit de faire, car les règles de transition le permettent. Dans le second, il ose aller vers d’autres états et arrive finalement dans l’état q₂, qui est final. Dans cette branche, l’automate accepterait le mot. Un automate non déterministe choisit toujours automatiquement la branche où le mot est accepté, si une telle branche existe.

Comment fait-il pour choisir automatiquement la « bonne » branche ? On peut se l’imaginer ainsi : l’automate non déterministe parcourt toutes les branches possibles, et s’il en trouve une où il accepte le mot, alors il accepte le mot. Comment peut-il parcourir toutes les branches ? Tout simplement : dès qu’il est dans un état d’où partent n arcs pour le symbole courant, l’automate se copie n fois, et chaque copie suit un chemin différent. Nous explorons ainsi peu à peu toutes les possibilités.

Représentation en arbre du calcul de l’automate

Modifions légèrement l’automate précédent :

Le non-déterminisme reste dans le premier état. L’automate précédent acceptait tous les mots qui se terminent par 01. Cet automate modifié accepte tous les mots qui contiennent le sous-mot 01. Il accepte donc par exemple le mot 101 ou 0101. On peut visualiser facilement toutes les branches du calcul à l’aide d’un arbre ; pour le mot 01010, l’arbre pourrait ressembler à ceci :

Au début, nous sommes dans l’état initial q₀. En entrée, nous avons le mot 01010, et le premier caractère non lu est 0. De l’état q₀ partent deux transitions pour le symbole 0, vers les états q₀ et q₁. L’arbre aura donc deux fils à ce nœud : q₀ et q₁. Nous lisons ensuite le symbole 1. Il n’y a là aucune ambiguïté : nous passons aux états q₀ et q₂. Puis nous lisons le caractère 0 ; dans la branche de gauche, l’ambiguïté réapparaît, et nous séparons le calcul en deux nouvelles branches. Dans l’une, nous restons de nouveau dans q₀, dans l’autre nous allons dans q₁. Et ainsi de suite.

Remarque que deux branches au total se terminent dans l’état q₂, un état final. Il existe donc deux branches de calcul par lesquelles l’automate peut accepter ce mot. Cet automate accepterait donc le mot 01010. Nous pouvons essayer de construire un arbre analogue pour le mot 1000.

Le calcul reste dans l’état q₀ ou passe dans l’état q₁, mais de là il ne peut plus aller nulle part, car il ne reste en entrée que des 0 et l’état q₁ n’a de transition que pour le symbole 1. Aucune branche du calcul ne se termine dans un état final, donc l’automate n’accepte pas le mot 1000.

ε-transitions

Dans les automates non déterministes, nous pouvons en plus utiliser des ε-transitions. Ce sont des transitions que nous pouvons effectuer quel que soit le symbole en entrée, et cela sans lire aucun symbole du mot. Comment pourrait-on écrire un automate non déterministe qui accepte le mot vide, tous les mots composés uniquement de 1, et les mots de la forme (10)ⁿ, c’est-à-dire 10, 1010, … ?

Nous avons séparé l’automate en deux « sous-automates ». Celui du haut s’occupe de reconnaître les mots composés de 1, celui du bas s’occupe des mots de la forme (10)ⁿ. Essayons d’accepter le mot 111. Au début, l’automate est dans l’état q₀ et le mot 111 est en entrée. Comme il dispose d’ε-transitions, il peut décider de passer dans l’état q₁ ou q₂, selon ce qui l’arrange. Nous voyons qu’il lui conviendra de passer dans l’état q₁. L’automate y va. Pendant ce temps, le mot 111 est toujours intact en entrée ! C’est seulement à ce moment qu’il commence à lire les symboles du mot et à passer de l’état q₁ à l’état q₁, jusqu’à ce qu’il ait lu tout le mot et l’accepte.

Si nous essayions d’accepter 1010, l’automate passerait au début dans l’état q₂, et ce n’est qu’à partir de là qu’il commencerait à traiter les symboles, et il accepterait de nouveau le mot.

Pour le mot 1100, l’automate peut faire n’importe quoi : il n’a aucun moyen d’accepter un tel mot.

Les ε-transitions et le non-déterminisme nous facilitent beaucoup le travail. Par exemple, la preuve que la réunion de deux langages réguliers est encore un langage régulier s’écrit bien plus simplement avec des ε-transitions que dans le cas des automates finis déterministes. Dans cette preuve, nous avions les exemples d’automates suivants

puis nous avions construit un automate fini déterministe qui acceptait la réunion des deux langages. Avec des ε-transitions, nous pouvons construire un tel automate ainsi :

Il suffit d’ajouter un nouvel état initial, d’où partent deux ε-transitions vers les anciens états initiaux des automates de départ, et c’est tout. L’automate décide de façon non déterministe s’il essaie d’accepter le mot avec l’un ou l’autre « sous-automate ».

Définition d’un automate non déterministe

Nous avons déjà vu en quoi un automate fini déterministe diffère d’un automate non déterministe ; il ne reste qu’à formaliser tout cela. Nous avons défini un automate fini déterministe comme un quintuplet (Q ; Σ ; δ ; q₀ ; F), où Q est l’ensemble des états, Σ est l’alphabet, δ est la fonction de transition, q₀ est l’état initial et F est l’ensemble des états finals. La seule chose qui change dans la définition des automates non déterministes est la définition de la fonction de transition.

Dans la version déterministe, la fonction δ(q, w) ne pouvait renvoyer qu’un seul état, alors que dans la version non déterministe, elle peut en renvoyer plusieurs, si plusieurs transitions sont définies pour un même symbole. Comme nous devons aussi définir les ε-transitions, notons Σ_ε l’ensemble Σ ∪ {ε}, c’est-à-dire Σ_ε = Σ ∪ {ε}. Nous définissons donc la fonction δ ainsi :

$δ : Q \times Σ_{ε} \to 2^{Q}$

La notation 2^Q désigne l’ensemble des parties, c’est-à-dire l’ensemble de tous les sous-ensembles de Q. La formalisation du calcul est très semblable à celle des automates finis. Une configuration de l’automate est de nouveau un couple (q ; w) ∈ Q × Σ^∗. L’étape de calcul ↦ est la relation sur l’ensemble des configurations telle que

$(q_{i}; w_{0} w_{1} \dots w_{n}) \mapsto (q_{j}; w_{1} \dots w_{n}),$

si et seulement si q_j ∈ δ(q_i, w₀). C’est dans cette phrase que se trouve la plus grande différence. Pour les automates déterministes, nous avions écrit cette condition q_j = δ(q_i, w₀), car la fonction δ renvoyait toujours un seul état. La version non déterministe de la fonction de transition renvoie un ensemble d’états, d’où le symbole ∈. La fermeture réflexive et transitive de la relation sera de nouveau notée ↦ ^∗. Nous disons que l’automate accepte le mot w si et seulement s’il existe q_f ∈ F tel que

$(q_{0}; w) \mapsto^{*} (q_{f}; ε) .$

Sources

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

« Précédent: Automate complet

Suivant: Simulation d’un AFN »