La construction des sous-ensembles transforme un automate non déterministe en un automate déterministe qui reconnaît exactement le même langage. Le principe tient en une phrase : un état du nouvel automate est l'ensemble des états où l'ancien pourrait se trouver.
L'automate de départ
| Depuis | a | b |
|---|---|---|
q0 (initial) | q0, q1 | q0 |
q1 | q2 | |
q2 (acceptant) | q2 | q2 |
Objectif
Dérouler la construction jusqu'à ce qu'aucun ensemble nouveau n'apparaisse, puis compter.
Pourquoi l'explosion n'a pas lieu ici
Un automate à états a sous-ensembles possibles, ce qui donne 8 ici. La construction n'en atteint qu'une partie, parce que la plupart des combinaisons ne correspondent à aucune lecture réelle. C'est le cas ordinaire : l'explosion exponentielle est un pire cas, rarement un cas.