Simulation d’un AFN

Si nous avons un automate non déterministe et que nous voulons savoir s’il accepte un mot donné, nous pouvons transformer l’automate en automate déterministe, nous pouvons essayer d’une manière ou d’une autre, ou bien utiliser un algorithme qui simule le fonctionnement de l’AFN.

Principe de l’algorithme

Montrons le principe sur un exemple bien choisi. Prenons cet automate :

C’est un automate fini non déterministe qui accepte un certain langage. Peu importe lequel pour le moment. Voyons à quoi peut ressembler le calcul d’un tel automate pour le mot d’entrée 11001. L’idée est la suivante : nous traitons un symbole du mot et nous regardons où nous pouvons aller grâce aux transitions multiples pour le même symbole. Nous mémorisons tous ces états et, à l’étape suivante, nous supposons que nous sommes « dans tous ces états en même temps » ; ce qui nous intéresse alors, c’est de savoir où nous pouvons aller ensuite à partir de ces états.

Nous allons donc mémoriser l’ensemble des états dans lesquels nous pouvons nous trouver, ainsi que la partie non lue du mot. Au début, nous avons donc le couple ({q₀} ; 11001). Nous commençons dans l’état q₀ (l’état initial) et le mot en entrée est 11001. L’automate ressemble à ceci ; l’état dans lequel nous sommes est surligné en rouge et en gras :

Le premier symbole est 1 ; de l’état q₀, il n’y a qu’une seule transition pour le symbole 1, donc nous arrivons dans l’état q₁. Nous mémorisons le couple ({q₁} ; 1001). L’automate ressemble à ceci :

Continuons. La partie non lue du mot est 1001, donc nous cherchons de nouveau les transitions pour 1. Il y en a maintenant deux : vers l’état q₀ et vers l’état q₃. Nous allons maintenant dans les deux états à la fois. Nous mémorisons donc le couple ({q₀ ; q₃} ; 001).

Quelle est la logique ? Nous savons qu’il existe un chemin pour aller de l’état initial à l’état q₃ avec le mot 11, et aussi à l’état q₀. Nous ne savons pas encore quelle branche nous sera utile, alors nous mémorisons simplement les deux. Continuons. Nous avons en entrée le symbole 0. Nous devons maintenant regarder à la fois les transitions partant de q₀ et celles partant de q₃. De l’état q₀ partent des transitions vers les états q₁ et q₂, de l’état q₃ part une transition vers q₁. Nous prenons en compte tous ces états, ce qui donne le couple ({q₁ ; q₂} ; 01) :

Mais nous n’en avons pas fini avec cette étape. Nous voyons que de l’état q₂ part une ε-transition vers l’état q₄. Nous savons qu’après une ε-transition, nous pouvons « aller n’importe quand », sans lire de caractère supplémentaire. Autrement dit, sans lire un autre symbole du mot d’entrée, nous pouvons encore passer dans l’état q₄. Nous ajoutons donc l’état q₄ aux états dans lesquels nous pouvons nous trouver : ({q₁ ; q₂ ; q₄} ; 01). Nous colorierions l’automate ainsi :

Ensuite, le symbole en entrée est 0. Regardons où nous pouvons aller à partir des trois états dans lesquels nous sommes. De q₁, nous ne pouvons aller nulle part, car il manque une transition pour 0. Le calcul s’arrête dans cette branche. De l’état q₄, nous n’allons nulle part non plus. De l’état q₂, nous retournons dans l’état q₂. Mais comme de l’état q₂ part de nouveau une ε-transition vers l’état q₄, nous pouvons aussi arriver dans l’état q₄. À partir de l’ensemble d’états {q₁ ; q₂ ; q₄}, pour le symbole 0, nous pouvons donc arriver à l’ensemble d’états {q₂ ; q₄}, ce qui donne le couple ({q₂ ; q₄} ; 1) :

Enfin, nous avons en entrée le symbole 1. De l’état q₂, nous n’allons nulle part, le calcul s’arrête dans cette branche. Mais de l’état q₄, nous arrivons dans les états q₃ et q₅. Nous obtenons le couple ({q₃ ; q₅} ; ε) :

L’automate a maintenant lu tout le mot et « se trouve » dans deux états : q₃, q₅. Comme au moins l’un d’eux est un état final, l’automate accepte le mot 11001.

Algorithme

Nous avons d’abord besoin d’une fonction qui prend en paramètre un ensemble d’états et calcule les états que l’on peut encore atteindre à l’aide des ε-transitions. L’entrée est donc un automate (Q ; Σ ; δ ; q₀ ; F) et un ensemble d’états States ; la sortie est un sur-ensemble de ces états, qui comprend les états atteignables par des ε-transitions. Nous appellerons cette opération l’ε-fermeture de l’ensemble States.

$\begin{aligned} Function E p s i l o n C l o s u r e ((Q; Σ; δ; q_{0}; F), S t a t e s) \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup {q} \cup δ (q, ε) \\ EndFor \\ If N e x t S t a t e s ∖ S t a t e s = \emptyset Do \\ Return S t a t e s \\ Else \\ Return E p s i l o n C l o s u r e ((Q; Σ; δ; q_{0}; F), N e x t S t a t e s) \\ EndIf \\ EndFunction \end{aligned}$

Nous utilisons cette fonction dans la fonction qui simule le fonctionnement de l’automate non déterministe. L’entrée est l’automate, le mot d’entrée w = w₁w₂… w_n et l’ensemble d’états dans lesquels l’automate se trouve actuellement. La sortie est soit la réponse Oui, soit la réponse Non, selon que l’automate accepte ou non le mot donné.

$\begin{aligned} Function C o m p u t e N F A ((Q; Σ; δ; q_{0}; F), w, S t a t e s) \\ If w = ϵ Do \\ If S t a t e s \cap F \neq \emptyset Do \\ Return OUI \\ Else \\ Return NON \\ EndIf \\ EndIf \\ N e x t S t a t e s \leftarrow \emptyset \\ ForEach q \in S t a t e s Do \\ N e x t S t a t e s \leftarrow N e x t S t a t e s \cup δ (q, w_{1}) \\ EndFor \\ N e x t S t a t e s \leftarrow E p s i l o n C l o s u r e ((Q; Σ; δ; q_{0}; F), N e x t S t a t e s) \\ Return C o m p u t e N F A ((Q; Σ; δ; q_{0}; F), w_{2} w_{3} \dots w_{n}, N e x t S t a t e s) \\ EndFunction \end{aligned}$

Si nous voulons vérifier que l’automate accepte le mot w, nous appelons la fonction ainsi : ComputeNFA((Q ; Σ ; δ ; q₀ ; F), w, EpsilonClosure((Q ; Σ ; δ ; q₀ ; F), {q₀})).

Sources

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

« Précédent: Automate fini non déterministe

Suivant: Déterminisation d’un AFN »