Construcció de subconjunts

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 $n$ estats, el DFA equivalent podria tenir fins $2^{n}$ 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 $M\equiv (Q,\Sigma ,\delta ,q_{0},F)$ un NFA. L'algorisme de Construcció de subconjunts permet trobar un DFA $M'\equiv (Q',\Sigma ,\delta ',q'_{0},F')$ de manera que $L(M)=L(M')$

Algorisme de construcció de subconjunts

Vegem un Pseudocodi per l'algorisme:

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

Apliquem ara l'algorisme al NFA de la següent figura:

Comencem obtenint la $\epsilon$ -clausura de l'estat d'arrencada del NFA, és a dir, el conjunt d'estats abastables des de l'estat inicial, consumint únicament $\epsilon$ -transicions .

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

Un cop tenim definit l'estat d'arrencada del nostre DFA, podem començar a completar els estats i transicions restants. Com sabem que S representa un conjunt d'estats del NFA inicial, només hem de fer transitar aquest conjunt amb cada símbol del nostre alfabet i estudiar a quins altres conjunts s'arriba. Si aquests altres conjunts no pertanyen a Q ', llavors els afegirem al nostre DFA, en el cas contrari, només haurem d'afegir noves transicions.
En el nostre cas, el nostre estat inicial S ={0,1,2,4,7}transita amb símbol 'a' a un nou conjunt ({3,8}), al qual calcularem la seva $\epsilon$-clausura per obtenir B ={0,1,2,3,4,6,7,8}.

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

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

Repetim el procés anterior usant ara l'altre símbol pertanyent al nostre alfabet.

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

Un cop creades totes les transicions possibles per al nostre estat inicial ( S ), continuem l'execució de l'algorisme amb cada un dels estats trobats prèviament. En aquesta iteració, obtenim un conjunt d'estats ja conegut, per la qual cosa, només haurem d'afegir la transició corresponent al nostre autòmat.

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

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

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

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

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

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

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

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

El conjunt d'estats d'acceptació del DFA resultant estarà format per tots aquells estats que continguin un estat final de l'NFA. En el nostre cas, el NFA inicial tenia un estat d'acceptació identificat com 10 . En el procés que hem seguit només hem obtingut un conjunt que contingui aquest estat ( E ), per la qual cosa aquest es convertirà en el nostre nou estat d'acceptació.

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

El DFA resultant quedaria d'aquesta forma:

Exemples

Exemple 1

$\Rightarrow$

Exemple 2

$\Downarrow$

Referències

• keller/Kelley, Dean. Teoria d'Autòmats i Llenguatges Formals. Prentice Hall, 1995. ISBN 0-13-518705-2. 
• Hopcroft, J., Motwani, R., i Ullman, J.. Introducció a la teoria d'autòmats, Llenguatges i Computació. Addison Wesley, 2002. ISBN 84-7829-056-7.