Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

Automates II : déterminisme et non-déterminisme
Article mis en ligne le 18 avril 2007
dernière modification le 28 mars 2023

Automates II : déterminisme et non-déterminisme

Automates II : déterminisme et non-déterminisme

Laurent Bloch

Cet article vient à la suite d’un autre : Automates et machines de Turing. Nous poursuivons ainsi, guidés par MM. Hopcroft et Ullmann[1], auxquels s’est joint Rajeev Motwani, notre tour de quelques outils formels de la linguistique de la programmation, qui n’a que peu à voir avec celle des langages humains, faut-il le préciser.

Ce nouveau chapitre introduit les automates à états fini non déterministes, et montre qu’ils sont équivalents à leurs cousins déterministes.



1. Automate à états fini non déterministe

Rappelons la définition de l’automate à états fini non déterministe (NFA) (pour le déterministe (DFA), voir : Automates et machines de Turing) :

  1. un ensemble fini d’états, souvent noté Q ;
  2. un ensemble fini de symboles, appelé alphabet et souvent noté Σ ;
  3. une fonction de transition, souvent nommée δ, qui reçoit comme arguments un état de Q et un symbole de Σ ou la chaîne vide notée є et qui rend comme résultat une partie de Q :
    δ : Q × (Σ ⋃ є ) → P(Q)
  4. un état initial q0, appartenant à Q ;
  5. un sous-ensemble F de Q constitué des états finals, ou états acceptants ;

soit le quintuplet A=(Q, Σ, δ, q0, F).

Un mot soumis à l'automate est une séquence de symboles de l'alphabet. Comme dans le cas déterministe, nous dirons que le mot w est accepté par l'automate s'il existe un chemin, étiqueté par les symboles consécutifs de w, entre l'état initial et un des états acceptants de l'automate.

L'ensemble des mots acceptés par l'automate constitue le langage reconnu par l'automate.

Voici un exemple d'automate à états fini non déterministe :


NFA simple

Figure 1: Automate fini non déterministe qui accepte tous les mots terminés par la chaîne 01.




Comment se représenter le traitement d'un mot en entrée par un tel automate ? Comme pour le cas déterministe, on peut imaginer une tête de lecture qui examine successivement chaque symbole du mot, et selon la valeur du symbole déclenche la transition appropriée : en outre, si plusieurs transitions sont possibles, l'automate se reproduit en autant d'exemplaires qu'il y a de chemins possibles et chaque automate poursuit sa route, en se reproduisant à nouveau le cas échéant. Le premier automate de la tribu qui atteint un état acceptant en ayant épuisé les symboles du mot a gagné ; si aucun chemin n'aboutit à un état acceptant, le mot soumis n'appartient pas au langage.

Cette multiplication des automates est représentée par le diagramme ci-dessous, dans le cas où l'automate de la figure 1 se voit soumettre le mot 00101 :


Prolifération du NFA simple








Figure 2: Multiplication des états de l'automate de la figure 1 pour le mot 00101.




Nous pouvons également représenter cet automate par sa table de transitions :

0 1
q0 {q0,q1} {q0}
 q1{q2}
*q2


Voici un autre exemple d'automate à états fini non déterministe :


Automate non déterministe

Figure 3: Automate fini non déterministe.




Dans ce cas la multiplication des automates est représentée par le diagramme ci-dessous, dans le cas où l'automate de la figure 3 se voit soumettre le mot 01001 :


Multiplication des états










Figure 4: Multiplication des états de l'automate de la figure 3 pour le mot 01001.






2. Équivalence NFA – DFA, exposé d’un exemple

Pour tout automate fini non déterministe (NFA) qui reconnaît un langage L il existe un automate fini déterministe (DFA) qui reconnaît le même langage. C'est un théorème, à démontrer donc ci-dessous.


Construction informelle des sous-ensembles d’états

La démonstration repose sur un procédé appelé la construction de sous-ensembles, parce qu’elle consiste à construire tous les sous-sensembles de l’ensemble des états du NFA.

La construction des sous-ensembles part d’un NFA
N=(QN, Σ, δN, q0, FN) pour produire un DFA
D=(QD, Σ, δD, q0, FD) tel que
L(D) = L(N).

On note que les alphabets d’entrée des deux automates N et D
sont les mêmes, et que l’état initial de D est l’ensemble qui contient comme unique élément l’état initial de N. Les autres éléments de D sont construits comme suit :

  1. QD est l’ensemble des sous-ensembles de QN ; si QN a
    n états, QD en aura 2n, ce qui se démontre par récurrence. Il arrive que certains de ces 2n états ne soient pas accessibles depuis l’état initial de QD ; ils peuvent être abandonnés, ainsi D pourra avoir moins de 2n états.
  2. FD est l’ensemble des sous-ensembles S de QN tel que
    SFN ≠ ∅. C’est-à-dire que FD comprend tous les ensembles d’états de N qui incluent au moins un état acceptant de N.
  3. Pour chaque ensemble SQN et pour chaque symbole d’entrée a de Σ,
    δD(S,a) =
     
    p dans S
    δN(p,a)

    C’est-à-dire que pour calculer δD(S,a) nous considérons, pour chaque état p dans S, quels sont les états que N peut atteindre à partir de p en recevant le symbole a, et nous prenons l’union de tous ces états.

Reprenons l'automate non déterministe de la figure 1 et envisageons la construction de l'ensemble de sous-ensembles qui lui correspond. Cet automate a trois états {q0, q1, q2}, la construction doit donc donner les 23 = 8 sous-ensembles de cet ensemble, qui correspondront aux 8 états de l'automate déterministe correspondant.

Voici la table de transition de ce DFA pour :

0 1
 
{q0} {q0,q1}{q0}
 {q1} {q2}
*{q2}
 {q0,q1}{q0,q1}{q0,q2}
*{q0,q2}{q0,q1}{q0}
*{q1,q2}{q2}
*{q0,q1,q2}{q0,q1}{q0,q2}


Pour une meilleure compréhension, nous pouvons renommer ces ensembles, qui sont les états du DFA, de noms plus simples, en l'occurrence des lettres :

0 1
 AAA
BEB
 CAD
*DAA
 EEF
*FEB
*GAD
*HEF


Il est de cette façon plus facile à voir que l'automate décrit par cette table de transitions est un DFA. Notons aussi que de l'état initial B, les seuls états accessibles sont B, E et F. Les cinq autres états sont inaccessibles, et peuvent être éliminés.


Calcul des sous-ensembles pour un exemple

La démonstration du théorème repose sur les idées exposées ci-dessus, et notamment sur la construction de l'ensemble des sous-ensembles des états du NFA, puis sur la sélection de ceux de ces états qui sont effectivement accessibles à partir à partir de l'état initial.

Nous voulons montrer que pour tout automate fini non déterministe (NFA) N qui reconnaît un langage L il existe un automate fini déterministe (DFA) D qui reconnaît le même langage. Nous allons ici, dans un premier temps, effectuer le calcul pour l'exemple de la section précédente. À la section suivante nous ferons le calcul qui donnela démonstration générale.

Base de l'induction :

Nous pouvons tenir pour assuré que le sous-ensemble des états de N constitué d'un élément unique, son état initial, est accessible.

Induction :

Supposons déterminé par les étapes précédentes un sous-ensemble S d'états accessibles : calculons pour chacun des symboles a l'ensemble des états δD(S,a) ; nous savons que ces ensembles d'états seront eux aussi accessibles.

Par exemple pour le NFA N de la figure 1, nous savons que l'état q0 sera un état du DFA D correspondant. Nous trouvons, par l'examen du diagramme de transitions, que δD({q0},0) = {q0,q1} et que δD({q0},1) = {q0} ; ce qui nous donne la seconde ligne de la table de transitions du DFA D.

Un des deux ensembles que nous venons de calculer était déjà connu : {q0} ; l'autre, {q0,q1}, est nouveau, et il nous faut calculer les transitions qui peuvent en être issues :

δD({q0,q1},1)=δN(q0, 1) ⋃ δN(q1, 1)
 ={q0} ⋃ {q2}
 ={q0,q2}

et de même :

δD({q0,q1},0) = {q0,q1}

Nous avons ainsi calculé la cinquième ligne de la table de transitions du DFA D et trouvé un nouvel état de D, {q0,q2}. De même :

δD({q0,q2},0)=δN(q0, 0) ⋃ δN(q2, 0)
 ={q0,q1} ⋃ ∅
 ={q0,q1}
δD({q0,q2},1)=δN(q0, 1) ⋃ δN(q2, 1)
 ={q0} ⋃ ∅
 ={q0}

Ces derniers calculs nous donnent la sixième ligne de la table de transitions de D, mais les ensembles d'états obtenus étaient déjà connus.

La construction des sous-ensembles a convergé, nous connaissons tous les états accessibles et leurs transitions. Nous pouvons maintenant exhiber le DFA équivalent au NFA de la figure 1 :


DFA simple




Figure 5: Automate fini déterministe qui accepte tous les mots terminés par la chaîne 01, équivalent au NFA de la figure 1.




Tous les graphes de cet article ont été calculés et dessinés au moyen
du merveilleux logiciel libre GraphViz. Il y a aussi un site francophone.



3. Le théorème d’équivalence DFA-NFA

Passons maintenant à la démonstration formelle, empruntée au livre classique de MM. Hopcroft et Ullmann[1], ou si l'on a la dernière édition, des mêmes plus M. Rajeev Motwani.

Définition préalable : fonction de transition étendue

Si δ est la fonction de transition d'un DFA D, nous notons d la fonction de transition étendue pour cet automate qui prend comme arguments un état q et une chaîne de caractères en entrée w, et qui rend comme résultat l'état dans lequel se trouve l'automate considéré après avoir traité w. Nous noterons |w| la longueur de w.

Si δ est la fonction de transition d'un NFA N, nous notons d la fonction de transition étendue pour cet automate qui prend comme arguments un état q et une chaîne de caractères en entrée w, et qui rend comme résultat l'ensemble des états dans lesquels peut se trouver l'automate considéré après avoir traité w.

Théorème 1 (Théorème) Si D = (QD, Σ, δD, {q0}, FD) est le DFA construit à partir du NFA N = (QN, Σ, δN, q0, FN) par construction des sous-ensembles d'états, alors L(D) = L(N).

Proof.[Démonstration : ]

Montrons d'abord, par induction sur |w|, que :

dD({q0},w) = dN(q0,w)

Notons que chacune des fonctions d retourne un ensemble d'états de QN, mais que dD interprète cet ensemble comme un des états de QD,qui est l'ensemble puissance de QN, cependant que dNinterprète cet ensemble comme un sous-ensemble de QN

Base :

Soit |w| = 0 ce qui revient à w = є ; de par les définitions de d pour les NFA et les DFA :

dD({q0},є) = dN(q0,є) = {q0}

Induction :

Supposons le résultat vrai pour un mot de longueur n, et soit le mot w de longueur n+1. Posons w = xa, ou a est le symbole final de w. De par l'hypothèse d'induction, dD({q0},x) = dN(q0,x). Posons que ces ensembles d'états de N s'écrivent {p1, p2, ..., pk}.

La définition de la fonction de transition étendue pour les NFA nous dit que :

dN(q0,w) =
k
i=1
δN (pi,a)

La construction de sous-ensembles, d'autre part, nous dit que :

δD({p1, p2, ..., pk}, a) =
k
i=1
δN (pi,a)

Utilisons ce dernier résultat, et la fait que dD({q0},x) = {p1, p2, ..., pk} de par la définition de d pour les DFA :

dD({q0},w)=δD(dD({q0},x),a)
 =δD({p1, p2, ..., pk}, a)
 =
k
i=1
δN (pi,a)

D'où nous déduisons :

dD({q0},w) = dN(q0,w)

Si nous remarquons que D et N acceptent chacun w si et seulement si dD({q0},w) ou dN(q0,w), respectivement, contiennent un état de FN, nous avons montré que L(D) = L(N).




Références

[1]
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automata Theory, Languages, and Computation. Addison Wesley, 1979 – 2007.


Index

  • automate
    • à états fini
      • déterministe, ??
      • non déterministe, ??


  • DFA, voir automate à états fini déterministe
  • langage
    • reconnu par un automate, ??


  • NFA, voir automate à états fini non déterministe

Ce document a été traduit de LATEX par HEVEA