L'algorithme qui dompte le chaos des automates

Imaginez une machine qui prend plusieurs chemins à la fois — c'est l'automate non déterministe. Or, les ordinateurs préfèrent les décisions uniques. La construction par sous-ensembles est le trick magique qui transforme ce chaos en ordre parfait. Cet algorithme convertit un automate fini non déterministe en automate fini déterministe équivalent, c'est-à-dire qu'il reconnaît exactement les mêmes langages. C'est remarquable : non seulement cette conversion est possible, mais elle repose sur un algorithme précis et maîtrisé. Un pont invisible mais fondamental entre l'indécidable et le décidable.