Usuario:Escaldon/Construcción de subconjuntos

En la teoría de la computación, la construcción de subconjuntos es un método estándar para convertir un NFA(Autómata Finito No Determinista) a un DFA(Autómata Finito Determinista) que reconoce 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 reconocer. Sin embargo si el NFA tiene $n$ estados, el DFA resultante podría tener hasta $2n$ estados, exponencialmente más. Eso resulta que a veces construir un DFA a partir de un NFA grande no es practicable.

[[Categoría:Lenguajes formales]] [[de:Potenzmengenkonstruktion]] [[en:Powerset construction]] [[it:Costruzione dei sottoinsiemi]] [[pl:Determinizacja automatu skończonego]] [[zh:幂集构造]] Sea $M\equiv (Q,\Sigma ,\delta ,q_{0},F)$ un NFA. El algoritmo de Construcción de subconjuntos permite hallar un DFA $M'\equiv (Q,\Sigma ,\delta ',q'_{0},F')$ de modo que $L(M)=L(M')$ (Reconozcan el mismo lenguaje).

Algoritmo de construcción de subconjuntos

Veamos un Pseudocódigo para el algoritmo:

$q'_{0}=S=\epsilon -clausura(q_{o});$

$desmarcar(S);$

$DFA\_states:=\{S\};$

While $(\exists \mathrm {T} \in DF\!A\_states\And \!\And !marcado(\mathrm {T} ))$ do 

   $marcar(\mathrm {T} );$ 

   For all $a\in \Sigma$ do

      $R:=\epsilon -clausura(\delta (\mathrm {T} ,a));$
      $\delta '(\mathrm {T} ,a):=R;$
      if (!($R\in DF\!A\_states))$ then 

         DFA_states := DFA_states $\cup \{R\};$

         desmarcar(R);

      end;
  end;
end;

Apliquemos ahora el algoritmo al NFA de la siguiente figura:

El estado inicial o estado de arranque del NFA es el que está marcado con una flecha y pone start en nuestro caso el 0. Empezamos haciendo la epsilon-clausura del estado de arranque del NFA( la epsilon-clausura conciste en ver, desde el estado al que se le hace, hasta que estados se puede llegar sin consumir ningun simbolo, es decir, con transiciones epsilon).

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

Transitamos con el primer símbolo de nuestro alfabeto.

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

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

Le hacemos la epsilon-clausura al conjunto resultante. El conjunto que nos da ( $\{0,1,2,3,4,6,7,8\}$ ) es diferente al que ya teníamos ( $\{0,1,2,4,7\}$ ), así que le asignamos otra letra, por ejemplo la B.

Transitamos con el segundo símbolo y hacemos lo mismo que en el paso anterior.

$\delta (S,b)=\{5\}$

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

Ahora pasamos al segundo estado del DFA que estamos construyendo. Y hacemos lo mismo en el paso anterior.

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

En caso de darnos un conjunto que ya teníamos, le asignamos la misma letra.

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

$\delta (B,b)=\{5,9\}$

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

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

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

$\delta (C,b)=\{5\}$

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

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

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

$\delta (D,b)=\{5,10\}$

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

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

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

$\delta (E,b)=\{5\}$

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

Ahora para ver cual sería el nuevo(o los nuevos) estados de aceptación, miramos en que conjunto cayó el anterior estado de aceptación (era el estado 10), en este caso solo cayó en el estado E( $\{1,2,4,5,6,7,$ 10 $\}$ ), así que nuestro único estado de aceptación en el DFA será el E (marcado con doble circulo).

El DFA resultante quedaría de esta forma:

{{Categorízame|Lenguajes formales|Autómatas finitos|Autómatas finitos deterministas|Autómatas finitos no deterministas}}