Construcció de subconjunts
From Wikipedia, the free encyclopedia
En la teoria de la computació, la Construcció de subconjunts és un mètode estàndard per a, partint d'un NFA (Autòmat Finit No Determinista), obtenir un DFA (Autòmat Finit Determinista) equivalent, és a dir, que reconegui el mateix Llenguatge regular. En la teoria és important perquè estableix que els NFA encara que són més flexibles, no poden reconèixer cap llenguatge que un DFA no pugui. No obstant això, donat un NFA amb estats, el DFA equivalent podria tenir fins
estats, per la qual cosa de vegades, construir un DFA a partir d'un NFA de grans dimensions no és practicable. Aquest problema es minimitza en gran manera amb l'algorisme de Construcció de subconjunts , el qual limita la inserció d'estats al DFA resultant únicament als casos estrictament necessaris.
Sigui un NFA. L'algorisme de Construcció de subconjunts permet trobar un DFA
de manera que