Construcción de subconjuntos

Veamos un Pseudocódigo para el algoritmo:

${\displaystyle q'_{0}}$ = S = ${\displaystyle \epsilon -clausura(q_{o})}$;
desmarcar(S);
DFA_states := {S};
While (${\displaystyle \exists }$ T ${\displaystyle \in }$ DFA_states and !marcado(T)) do
   marcar (T);
   For all a ${\displaystyle \in \Sigma }$ do
      R := ${\displaystyle \epsilon -clausura(\delta }$(T, a));
      ${\displaystyle \delta '}$(T, a) := R;
      if (!(R ${\displaystyle \in }$ DFA_states)) then
         DFA_states := DFA_states ${\displaystyle \cup }$ {R};
         desmarcar(R);
      end;
  end;
end;

Apliquemos ahora el algoritmo al NFA de la siguiente figura:

Empezamos obteniendo la ${\displaystyle \epsilon }$-clausura del estado de arranque del NFA, es decir, el conjunto de estados alcanzables desde el estado inicial, consumiendo únicamente ${\displaystyle \epsilon }$-transiciones.

${\displaystyle \epsilon -clausura(0)=\{0,1,2,4,7\}=S=q'_{0}\,}$

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 ${\displaystyle \epsilon }$-clausura para obtener B = {0,1,2,3,4,6,7,8}.

${\displaystyle \delta (S,\,a)=\{3,8\}}$

${\displaystyle \epsilon -clausura(\{3,8\})=\{1,2,3,4,6,7,8\}=B\Rightarrow \delta '(S,a)=B}$

Repetimos el proceso anterior usando ahora el otro símbolo perteneciente a nuestro alfabeto.

${\displaystyle \delta (S,\,b)=\{5\}}$
${\displaystyle \epsilon -clausura(\{5\})=\{1,2,4,5,6,7\}=C\Rightarrow \delta '(S,b)=C}$

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.

${\displaystyle \delta (B,\,a)=\{3,8\}}$
${\displaystyle \epsilon -clausura(\{3,\,8\})=B\Rightarrow \delta '(B,\,a)=B}$

${\displaystyle \delta (B,\,b)=\{5,9\}}$
${\displaystyle \epsilon -clausura(\{5,9\})=\{1,2,4,5,6,7,9\}=D\Rightarrow \delta '(B,\,b)=D}$

${\displaystyle \delta (C,\,a)=\{3,8\}}$
${\displaystyle \epsilon -clausura(\{3,8\})=B\Rightarrow \delta '(C,\,a)=B}$

${\displaystyle \delta (C,\,b)=\{5\}}$
${\displaystyle \epsilon -clausura(\{5\})=C\Rightarrow \delta '(C,\,b)=C}$

${\displaystyle \delta (D,\,a)=\{3,8\}}$
${\displaystyle \epsilon -clausura(\{3,8\})=B\Rightarrow \delta '(D,\,a)=B}$

${\displaystyle \delta (D,\,b)=\{5,10\}}$
${\displaystyle \epsilon -clausura(\{5,10\})=\{1,2,4,5,6,7,10\}=E\Rightarrow \delta '(D,\,b)=E}$

${\displaystyle \delta (E,\,a)=\{3,8\}}$
${\displaystyle \epsilon -clausura(\{3,8\})=B\Rightarrow \delta '(E,\,a)=B}$

${\displaystyle \delta (E,\,b)=\{5\}}$
${\displaystyle \epsilon -clausura(\{5\})=C\Rightarrow \delta '(E,\,b)=C}$

El conjunto de estados de aceptación del DFA resultante estará formado por todos aquellos estados que contengan un estado final del NFA. 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.

${\displaystyle F'=\{q\in Q'\,|\,q\cap F\neq \emptyset \}}$

El DFA resultante quedaría de esta forma:

${\displaystyle \Rightarrow }$

• Kelley, Dean (1995). Teoría de Autómatas y Lenguajes Formales. Prentice Hall. ISBN 0-13-518705-2.
• Hopcroft, J., Motwani, R., y Ullman, J. (2002). Introducción a la teoría de Autómatas, Lenguajes y Computación. Addison Wesley. ISBN 84-7829-056-7.

• JFLAP, software para experimentar con lenguajes formales y autómatas