Construcția subseturilor

În teoria limbajelor formale , construcția subseturilor sau a construcției subseturilor este tehnica de construcție a automatului determinist finit echivalent cu un automat de stare finită nedeterminist .

Echivalența dintre automatul determinist și cel nedeterminist

Având în vedere un automat finit nedeterminist

NFA=\left\{Q_{N},\Sigma ,\delta _{N},q_{0},F_{N}\right\}

{\ displaystyle NFA = \ left \ {Q_ {N}, \ Sigma, \ delta _ {N}, q_ {0}, F_ {N} \ right \}}

{\ displaystyle NFA = \ left \ {Q_ {N}, \ Sigma, \ delta _ {N}, q_ {0}, F_ {N} \ right \}}

,

este posibil să se determine un automat finit determinist echivalent

DFA=\left\{Q_{D},\Sigma ,\delta _{D},\left\{q_{0}\right\},F_{D}\right\}

{\ displaystyle DFA = \ left \ {Q_ {D}, \ Sigma, \ delta _ {D}, \ left \ {q_ {0} \ right \}, F_ {D} \ right \}}

{\ displaystyle DFA = \ left \ {Q_ {D}, \ Sigma, \ delta _ {D}, \ left \ {q_ {0} \ right \}, F_ {D} \ right \}}

,

astfel încât $L\left(NFA\right)=L\left(DFA\right)$ ${\ displaystyle L \ left (NFA \ right) = L \ left (DFA \ right)}$ ${\ displaystyle L \ left (NFA \ right) = L \ left (DFA \ right)}$ . Ansamblul stărilor devine

Q_{D}={\mathcal {P}}\left(Q_{N}\right)\Rightarrow \left|Q_{D}\right|=2^{\left|Q_{N}\right|}

{\ displaystyle Q_ {D} = {\ mathcal {P}} \ left (Q_ {N} \ right) \ Rightarrow \ left | Q_ {D} \ right | = 2 ^ {\ left | Q_ {N} \ right |}}

{\ displaystyle Q_ {D} = {\ mathcal {P}} \ left (Q_ {N} \ right) \ Rightarrow \ left | Q_ {D} \ right | = 2 ^ {\ left | Q_ {N} \ right |}}

,

ansamblul stărilor finale

F_{D}=\left\{s\in Q_{D}|s\cap F_{N}\neq \emptyset \right\}

{\ displaystyle F_ {D} = \ left \ {s \ în Q_ {D} | s \ cap F_ {N} \ neq \ emptyset \ right \}}

{\ displaystyle F_ {D} = \ left \ {s \ în Q_ {D} | s \ cap F_ {N} \ neq \ emptyset \ right \}}

în timp ce noua funcție de tranziție este calculată ca:

\delta _{D}\left(s,a\right)=\bigcup _{p\in s}\delta _{N}\left(p,a\right),\forall s\in Q_{D}

{\ displaystyle \ delta _ {D} \ left (s, a \ right) = \ bigcup _ {p \ in s} \ delta _ {N} \ left (p, a \ right), \ forall s \ in Q_ {D}}

{\ displaystyle \ delta _ {D} \ left (s, a \ right) = \ bigcup _ {p \ in s} \ delta _ {N} \ left (p, a \ right), \ forall s \ in Q_ {D}}

unde funcția ${\mathcal {P}}\left(\cdot \right)$ ${\ displaystyle {\ mathcal {P}} \ left (\ cdot \ right)}$ ${\ displaystyle {\ mathcal {P}} \ left (\ cdot \ right)}$ indică ansamblul părților . Este posibil să se arate că automatul determinist astfel definit se dovedește a fi echivalent cu automatul nedeterminist din care este construit. Prin urmare, ambele automate recunosc același limbaj .

Algoritm de construcție pentru subseturi

Algoritmul pentru construirea automatului echivalent derivă direct din definiția automatului. Definiția funcției de tranziție $\delta$ ${\ displaystyle \ delta}$ $\ delta$ este evaluat pentru fiecare element aparținând domeniului $Q_{D}$ ${\ displaystyle Q_ {D}}$ ${\ displaystyle Q_ {D}}$ , adică pentru toate subseturile posibile ale $Q_{N}$ ${\ displaystyle Q_ {N}}$ ${\ displaystyle Q_ {N}}$ .

Evaluare leneșă

Este posibil ca construcția automatului echivalent prin intermediul algoritmului de construcție prin subseturi să poată duce la definirea stărilor inaccesibile, a căror prezență este redundantă și care duce la un exces de calcul care poate fi redus. Evaluarea leneșă permite evitarea calculelor necesare pentru a defini stările care nu sunt atinse de automat. Acest algoritm este definit inductiv prin faptul că nu se iau în considerare toate elementele întregii părți.
Baza: $\left\{q_{0}\right\}$ ${\ displaystyle \ left \ {q_ {0} \ right \}}$ ${\ displaystyle \ left \ {q_ {0} \ right \}}$ este o stare accesibilă.
Ipoteză inductivă: $s$ ${\ displaystyle s}$ $s$ a fost accesibil.
Pas inductiv: $\forall a\in \Sigma$ ${\ displaystyle \ forall a \ in \ Sigma}$ ${\ displaystyle \ forall a \ in \ Sigma}$ , $\delta \left(s,a\right)$ ${\ displaystyle \ delta \ left (s, a \ right)}$ ${\ displaystyle \ delta \ left (s, a \ right)}$ accesibil.
Evaluarea leneșă conduce la determinarea tuturor și numai a stărilor accesibile. Prin urmare, definiția funcției de tranziție poate fi realizată numai în aceste stări.

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe Subset Construction