En teoría de la computación, la Construcción de subconjuntos es un método estándar para, partiendo de un NFA (Autómata Finito No Determinista), obtener un DFA (Autómata Finito Determinista) equivalente, es decir, que reconozca el mismo Lenguaje regular.
En la teoría es importante porque establece que los NFAs aunque son más flexibles, no pueden reconocer ningún lenguaje que un DFA no pueda.
estados, el DFA equivalente podría tener hasta
estados, por lo que a veces, construir un DFA a partir de un NFA de gran tamaño no es practicable.
Una vez que tenemos definido el estado de arranque de nuestro DFA, podemos empezar a completar los estados y transiciones restantes.
Como sabemos que S representa un conjunto de estados del NFA inicial, sólo tenemos que hacer transitar dicho conjunto con cada símbolo de nuestro alfabeto y estudiar a que otros conjuntos se llega.
Si estos otros conjuntos no pertenecen a Q', entonces los añadiremos a nuestro DFA, en el caso contrario, sólo tendremos que añadir nuevas transiciones.
En nuestro caso, nuestro estado inicial S = {0,1,2,4,7} transita con símbolo 'a' a un nuevo conjunto ({3,8}), al cual calcularemos su
Repetimos el proceso anterior usando ahora el otro símbolo perteneciente a nuestro alfabeto.
Una vez creadas todas las transiciones posibles para nuestro estado inicial (S), continuamos la ejecución del algoritmo con cada uno de los estados encontrados previamente.
En esta iteración, obtenemos un conjunto de estados ya conocido, por lo cual, solo tendremos que añadir la transición correspondiente a nuestro autómata.
En nuestro caso, el NFA inicial tenía un estado de aceptación identificado como 10.
En el proceso que hemos seguido sólo hemos obtenido un conjunto que contenga éste estado (E), por lo cual este se convertirá en nuestro nuevo estado de aceptación.