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. 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 d'états peut être atteint, alors l'ensemble des états accessibles par la lecture de la lettre suivante est une fonction déterministe de et de .