Construction par sous-ensembles

En informatique théorique, et notamment en théorie des automates, l'algorithme appelé la construction par sous-ensembles, en anglais « powerset construction » ou « subset construction », est la méthode usuelle pour convertir un automate fini non déterministe (abrégé en « AFN ») en un automate fini déterministe (abrégé en « AFD ») équivalent, c'est-à-dire qui reconnaît le même langage rationnel.

L'existence même d'une conversion, et l'existence d'un algorithme pour la réaliser, est remarquable et utile. Elle est remarquable parce qu'il existe peu de modèles de machines pour lesquels les versions déterministe et non déterministe ont la même puissance de reconnaissance : ainsi, les automates à pile déterministes sont moins puissants que les automates à pile généraux. Elle est utile dans la pratique parce que la reconnaissance par un automate déterministe est bien plus facile à mettre en œuvre que la reconnaissance par automate non déterministe. Toutefois, la construction par sous-ensembles peut produire un automate dont la taille, mesurée en nombre d'états, est exponentielle par rapport à la taille de l'automate de départ.

La construction par sous-ensembles a été publiée pour la première fois par Michael O. Rabin et Dana S. Scott dans un article fondateur paru en 1959. Ils ont obtenu le prix Turing pour leurs travaux autour du non-déterminisme en 1976.

Description intuitive

Pour décrire le comportement d'un automate fini déterministe sur une entrée donnée, il suffit de conserver la trace d'un seul état à chaque instant, à savoir l’état atteint après avoir lu le début du mot donné en entrée.

Dans le cas d'un automate fini non déterministe, on doit conserver la trace d'un ensemble d'états, à savoir tous les états qui sont atteints, après la lecture d'un début du mot d'entrée, selon le choix des transitions qui ont été faites. Si, par la lecture d'un début de l'entrée, un ensemble $P$ d'états peut être atteint, alors l'ensemble des états accessibles par la lecture de la lettre suivante $a$ est une fonction déterministe de $P$ et de $a$. C'est pourquoi les ensembles d'états accessibles dans un automate non déterministe peuvent jouer le rôle d'états dans un automate déterministe, chaque tel ensemble étant interprété comme un seul état de l'automate déterministe.

Construction

La construction par sous-ensembles s'applique en général aux automates finis non déterministes sans $\varepsilon$-transitions. Un tel automate ${\mathcal {A}}$, sur un alphabet $A$, est composé d'un ensemble fini d'états $Q$, d'un ensemble d'états initiaux $I$, d'un ensemble d'états terminaux $T$ et d'un ensemble de transitions ${\mathcal {F}}$. On trouve aussi la description sous forme de quintuplet

${\mathcal {A}}=(Q,{\mathcal {F}},I,T,A)$ .

L'automate fini déterministe correspondant a pour états des parties de $Q$. L'état initial est l'ensemble $I$ ; la fonction de transition est la fonction $\delta$ qui, pour une partie $P$ de $Q$ et une lettre $a$ donne l'ensemble $\delta (P,a)=\{q\mid \exists p\in P,(p,a,q)\in {\mathcal {F}}\}$. C'est donc l'ensemble des états atteints, dans l'automate de départ, par une transition qui débute en un état de $P$ et qui porte l’étiquette $a$. Une partie de $Q$ est un état final de l'automate déterministe si elle contient au moins un état de $T$.

Dans la version la plus simple, l'ensemble d'états de l'automate déterministe est l'ensemble des parties de Q. Mais il se peut que de nombreux états de cet automate sont inutiles parce qu'ils ne sont pas accessibles à partir de l’état initial. C'est pourquoi on réalise en général l'opération en ne construisant que les états accessibles. Pour cela, on maintient une structure de données qui conserve les états de l'automate en construction et dont les images par la fonction $\delta$ n'ont pas encore été construites; on puise des ensembles dans cette structure, on construit l'image par $\delta$, et on l'ajoute à la structure si elle est nouvelle. Ce procédé revient donc à faire la construction de l'automate tout en réalisant un parcours du graphe sous-jacent.

Avec des petites modifications, l'algorithme s'applique aussi à des variantes des automates non déterministes. Ainsi, la présence d'$\varepsilon$-transitions modifie comme suit la construction: au lieu de prendre comme état initial l'ensemble I, on prend l'ensemble des états accessibles à partir de I par des chemins composés uniquement d'$\varepsilon$-transitions. De même, pour la fonction de transition, la valeur $\delta (P,a)$ est l'ensemble des états accessibles par un chemin formé d'$\varepsilon$-transitions et d'une transition étiquetée $a$.

Un exemple

Automate non déterministe.

Automate déterministe obtenu par la construction par sous-ensembles.

L'automate ci-contre possède quatre états : 1 est initial, 3 et 4 sont terminaux. L'alphabet est formé des symboles 0 and 1, et il a deux ε-transitions.

L'état initial de l’automate déterministe construit à partir de l'automate de départ est l'ensemble des états accessibles depuis 1 par des chemins formés d'ε-transitions ; c'est l'ensemble {1,2,3}. Une transition de {1,2,3} par le symbole 0 utilise soit la flèche de l'état 1 vers l'état 2, ou celle de l'état 3 vers l'état 4. Par ailleurs, ni l'état 2 ni l'état 4 sont le début d'une ε-transitions, et par conséquent δ({1,2,3},0) = {2,4}. En appliquant le même raisonnement, on construit l'automate déterministe en entier. Seuls cinq des états de l'automate déterministe sont accessibles depuis l'état initial; les onze ensembles restants de l’ensemble des parties ne sont pas accessibles.

Complexité et propriétés

Un automate non déterministe avec n = 5 états, et l'automate déterministe équivalent qui demande 2^n-1 = 16 états.

Un automate non déterministe à $n$ états peut être converti, par la méthode des sous-ensembles, en un automate déterministe équivalent ayant au plus $2^{n}$ états. De fait, il existe des automates non déterministes à $n$ états pour lesquels les automates déterministes équivalents ont approximativement $2^{n}$ états, de sorte que la complexité en espace et donc aussi la complexité en temps dans le pire cas est $O(2^{n})$. Un exemple simple qui approche cette limite est le langage des mots sur l'alphabet {0,1} de longueur au moins $n$, dans lequel la $n$-ième lettre depuis la fin est un 1. On peut représenter ce langage par un automate à $n+1$ états, un pour chacun des suffixes du mot. Il existe des automates qui atteignent exactement la borne $2^{n}$. Un tel exemple a été donné par Oleg Lupanov en 1963.

Applications

Brzozowski a développé un algorithme pour la minimisation d'un automate fini déterministe qui utilise deux fois la construction par sous-ensembles. Il convertit l'automate de départ en un automate qui reconnaît l'image miroir du langage, en inversant le sens des flèches, et en échangeant le rôle des états initiaux et terminaux. Il convertit cet automate en un automate déterministe par la construction des sous-ensembles, puis il recommence l'opération en transposant à nouveau l'automate et en le convertissant en automate déterministe. Il est tout à fait étonnant que cette méthode permet d'obtenir l'automate minimal de l'automate de départ. La complexité de cet algorithme, composé d'opération simples, est exponentielle dans le pire des cas.

La construction de Safra , qui convertit un automate de Büchi non déterministe à $n$ états en un automate de Muller déterministe ou un automate de Rabin à $2^{O(n\log n)}$ états, utilise aussi la construction par sous-ensembles comme brique de son algorithme.

Bibliographie

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Powerset construction » (voir la liste des auteurs).
• Michael Sipser, Introduction to the Theory of Computation, 1997, 396 p. (ISBN 978-0-534-94728-6 et 0-534-94728-X), p. 55. Section 1.2, Théorème 1.19.
• John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Reading Massachusetts, Addison-Wesley Publishing, 1979 (ISBN 0-201-02988-X), Chapitre 2.
• James A. Anderson et Thomas J. Head, Automata theory with modern applications, Cambridge University Press, 2006, 264 p. (ISBN 978-0-521-84887-9, lire en ligne), p. 43–49
• Klaus Schneider, Verification of reactive systems : formal methods and algorithms, Springer, 2004, 602 p. (ISBN 978-3-540-00296-3, lire en ligne), p. 210–212.
• Michael O. Rabin et Dana Scott, « Finite automata and their decision problems », IBM Journal of Research and Development, vol. 3, n^o 2,‎ 1959, p. 114–125 (DOI 10.1147/rd.32.0114).