Automat cu stare finită nedeterminist

Exemplu ASFND

În teoria calculului, un automat cu stare finită nedeterministică (ASFND, în engleză nondeterministic finite automaton, NFA) este o mașină cu stări finite în care pentru fiecare pereche intrarea simbol-stare poate avea mai multe stări de destinație.

Spre deosebire de automatele finite deterministe , NFA-urile pot schimba starea independent de simbolul citit, prin tranziții epsilon . Automatele care prezintă acest tip de tranziții se mai numesc ε-NFA.

Definiție formală

Un automat finit nedeterminist este un cvintuplu ${\mathcal {A}}=\left\langle \Sigma ,S,\delta ,s_{0},F\right\rangle$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, S, \ delta, s_ {0}, F \ right \ rangle}$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, S, \ delta, s_ {0}, F \ right \ rangle}$ cu:

$\Sigma =\{a_{0},a_{1},\ldots ,a_{n}\}$ ${\ displaystyle \ Sigma = \ {a_ {0}, a_ {1}, \ ldots, a_ {n} \}}$ ${\ displaystyle \ Sigma = \ {a_ {0}, a_ {1}, \ ldots, a_ {n} \}}$ set finit de simboluri numit alfabet
$S=\{s_{0},s_{1},\ldots ,s_{m}\}$ ${\ displaystyle S = \ {s_ {0}, s_ {1}, \ ldots, s_ {m} \}}$ ${\ displaystyle S = \ {s_ {0}, s_ {1}, \ ldots, s_ {m} \}}$ ansamblu finit de stări
$\delta :S\times \Sigma \to P(S)$ ${\ displaystyle \ delta: S \ times \ Sigma \ to P (S)}$ ${\ displaystyle \ delta: S \ times \ Sigma \ to P (S)}$ funcție de tranziție , unde $P(S)$ ${\ displaystyle P (S)}$ ${\ displaystyle P (S)}$ este ansamblul părților lui S
$s_{0}\in S$ ${\ displaystyle s_ {0} \ în S}$ ${\ displaystyle s_ {0} \ în S}$ stare initiala
$F\subseteq S$ ${\ displaystyle F \ subseteq S}$ ${\ displaystyle F \ subseteq S}$ set de stări finale

Având un NFA ${\mathcal {A}}=\left\langle \Sigma ,S,\delta ,s_{0},F\right\rangle$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, S, \ delta, s_ {0}, F \ right \ rangle}$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, S, \ delta, s_ {0}, F \ right \ rangle}$ și un șir $w\in \Sigma ^{*}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ ${\ displaystyle w \ in \ Sigma ^ {*}}$ , A acceptă șirul $w=x_{1}x_{2}\cdots x_{n}$ ${\ displaystyle w = x_ {1} x_ {2} \ cdots x_ {n}}$ ${\ displaystyle w = x_ {1} x_ {2} \ cdots x_ {n}}$ cu $x_{i}\in \Sigma$ ${\ displaystyle x_ {i} \ in \ Sigma}$ ${\ displaystyle x_ {i} \ in \ Sigma}$ dacă există o succesiune de stări $R=\left\{r_{0},r_{1},\cdots ,r_{n}\right\}$ ${\ displaystyle R = \ left \ {r_ {0}, r_ {1}, \ cdots, r_ {n} \ right \}}$ ${\ displaystyle R = \ left \ {r_ {0}, r_ {1}, \ cdots, r_ {n} \ right \}}$ astfel încât:

$r_{0}=s_{0}$ ${\ displaystyle r_ {0} = s_ {0}}$ ${\ displaystyle r_ {0} = s_ {0}}$
$\delta (r_{i},x_{i})\in R$ ${\ displaystyle \ delta (r_ {i}, x_ {i}) \ în R}$ ${\ displaystyle \ delta (r_ {i}, x_ {i}) \ în R}$
$\delta (r_{i},x_{n})\cap F\neq \emptyset$ ${\ displaystyle \ delta (r_ {i}, x_ {n}) \ cap F \ neq \ emptyset}$ ${\ displaystyle \ delta (r_ {i}, x_ {n}) \ cap F \ neq \ emptyset}$

Aparatul pornește din starea inițială și citește un șir. Prin relația de tranziție $\delta$ ${\ displaystyle \ delta}$ $\ delta$ starea sau stările de destinație sunt determinate pe baza stării curente și a simbolului citit. Dacă după citirea ultimului simbol aparatul se află în cel puțin una dintre stările aparținând lui F, aparatul acceptă șirul, altfel îl respinge. Setul tuturor șirurilor acceptate de automatul de stare finită nedeterminist este limbajul acceptat de automat.

Limbajul acceptat de automatele finite nedeterministe este un limbaj obișnuit .

Echivalența dintre automatul nedeterminist și determinist

Pentru orice automat cu stare finită nedeterministă este posibil să se construiască un automat cu stare finită determinist capabil să recunoască același limbaj folosind construcția subseturilor .

Automat cu stare finită nedeterminist cu tranziții epsilon

Este posibil să se definească o variantă a automatelor finite nedeterministe care să permită tranziții de stare spontane, adică tranziții pe un șir gol $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ . Pentru astfel de automate este suficient să se redefinească funcția de tranziție ca:

\delta \left(Q\times \left(\Sigma \cup \left\{\varepsilon \right\}\right)\right)\rightarrow {\mathcal {P}}\left(Q\right)

{\ displaystyle \ delta \ left (Q \ times \ left (\ Sigma \ cup \ left \ {\ varepsilon \ right \} \ right) \ right) \ rightarrow {\ mathcal {P}} \ left (Q \ right) }

{\ displaystyle \ delta \ left (Q \ times \ left (\ Sigma \ cup \ left \ {\ varepsilon \ right \} \ right) \ right) \ rightarrow {\ mathcal {P}} \ left (Q \ right) }

.

Funcția de închidere $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$

Funcția de închidere activată $\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$ $\varepsilon -closure\left(\cdot \right)$ ${\ displaystyle \ varepsilon -closure \ left (\ cdot \ right)}$ ${\ displaystyle \ varepsilon -closure \ left (\ cdot \ right)}$ este definit inductiv.
Baza: $q\in \varepsilon -closure\left(q\right)$ ${\ displaystyle q \ in \ varepsilon -closure \ left (q \ right)}$ ${\ displaystyle q \ in \ varepsilon -closure \ left (q \ right)}$ .
Ipoteză inductivă: $p\in \varepsilon -closure\left(q\right)$ ${\ displaystyle p \ in \ varepsilon -closure \ left (q \ right)}$ ${\ displaystyle p \ in \ varepsilon -closure \ left (q \ right)}$ .
Pas inductiv: $\delta \left(p,\varepsilon \right)=\left\{r_{1},...,r_{n}\right\}\subseteq \varepsilon -closure\left(q\right)$ ${\ displaystyle \ delta \ left (p, \ varepsilon \ right) = \ left \ {r_ {1}, ..., r_ {n} \ right \} \ subseteq \ varepsilon -closure \ left (q \ right) }$ ${\ displaystyle \ delta \ left (p, \ varepsilon \ right) = \ left \ {r_ {1}, ..., r_ {n} \ right \} \ subseteq \ varepsilon -closure \ left (q \ right) }$ .

Funcție de tranziție extinsă

Funcția de tranziție extinsă ${\hat {\delta }}\left(\cdot \right)$ ${\ displaystyle {\ hat {\ delta}} \ left (\ cdot \ right)}$ ${\ displaystyle {\ hat {\ delta}} \ left (\ cdot \ right)}$ trebuie redefinit în termeni de $\varepsilon -closure$ ${\ displaystyle \ varepsilon -closure}$ ${\ displaystyle \ varepsilon -closure}$ după cum urmează:
Baza: ${\hat {\delta }}\left(q,\varepsilon \right)=\varepsilon -closure\left(q\right)$ ${\ displaystyle {\ hat {\ delta}} \ left (q, \ varepsilon \ right) = \ varepsilon -closure \ left (q \ right)}$ ${\ displaystyle {\ hat {\ delta}} \ left (q, \ varepsilon \ right) = \ varepsilon -closure \ left (q \ right)}$ .
Ipoteză inductivă: ${\hat {\delta }}\left(q,z\right)=\left\{p_{1},...,p_{k}\right\}$ ${\ displaystyle {\ hat {\ delta}} \ left (q, z \ right) = \ left \ {p_ {1}, ..., p_ {k} \ right \}}$ ${\ displaystyle {\ hat {\ delta}} \ left (q, z \ right) = \ left \ {p_ {1}, ..., p_ {k} \ right \}}$ .
Pas inductiv: $\omega =za\wedge \bigcup _{i=1}^{k}\delta \left(p_{i},a\right)=\left\{r_{1},...,r_{m}\right\}\Rightarrow {\hat {\delta }}\left(q,\omega \right)=\bigcup _{i=1}^{m}\varepsilon -closure\left(r_{i}\right)$ ${\ displaystyle \ omega = za \ wedge \ bigcup _ {i = 1} ^ {k} \ delta \ left (p_ {i}, a \ right) = \ left \ {r_ {1}, ..., r_ {m} \ right \} \ Rightarrow {\ hat {\ delta}} \ left (q, \ omega \ right) = \ bigcup _ {i = 1} ^ {m} \ varepsilon -closure \ left (r_ {i } \ dreapta)}$ ${\ displaystyle \ omega = za \ wedge \ bigcup _ {i = 1} ^ {k} \ delta \ left (p_ {i}, a \ right) = \ left \ {r_ {1}, ..., r_ {m} \ right \} \ Rightarrow {\ hat {\ delta}} \ left (q, \ omega \ right) = \ bigcup _ {i = 1} ^ {m} \ varepsilon -closure \ left (r_ {i } \ dreapta)}$ .

Exemplu

Următorul exemplu prezintă un automat finit nedeterminist $LA$ ${\ displaystyle A}$ $LA$ , pe alfabetul binar , capabil să determine dacă șirul de intrare conține un număr par de zero sau unul.

${\mathcal {A}}=\left\langle \Sigma ,S,\delta ,s_{0},F\right\rangle$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, S, \ delta, s_ {0}, F \ right \ rangle}$ ${\ displaystyle {\ mathcal {A}} = \ left \ langle \ Sigma, S, \ delta, s_ {0}, F \ right \ rangle}$ unde este

$\Sigma =\left\{0,1\right\}$ ${\ displaystyle \ Sigma = \ left \ {0,1 \ right \}}$ ${\ displaystyle \ Sigma = \ left \ {0,1 \ right \}}$
$S=\left\{S_{0},S_{1},S_{2},S_{3},S_{4}\right\}$ ${\ displaystyle S = \ left \ {S_ {0}, S_ {1}, S_ {2}, S_ {3}, S_ {4} \ right \}}$ ${\ displaystyle S = \ left \ {S_ {0}, S_ {1}, S_ {2}, S_ {3}, S_ {4} \ right \}}$
$s_{0}=S_{0}$ ${\ displaystyle s_ {0} = S_ {0}}$ ${\ displaystyle s_ {0} = S_ {0}}$
$F=\left\{S_{1},S_{3}\right\}$ ${\ displaystyle F = \ left \ {S_ {1}, S_ {3} \ right \}}$ ${\ displaystyle F = \ left \ {S_ {1}, S_ {3} \ right \}}$
Funcția de tranziție $\delta$ ${\ displaystyle \ delta}$ $\ delta$ este definit de următorul tabel de tranziție:

	0	1	$\varepsilon$ ${\ displaystyle \ varepsilon}$ $\ varepsilon$
$S_{0}$ ${\ displaystyle S_ {0}}$ $S_0$	$\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	$\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$	$\left\{S_{1},S_{3}\right\}$ ${\ displaystyle \ left \ {S_ {1}, S_ {3} \ right \}}$ ${\ displaystyle \ left \ {S_ {1}, S_ {3} \ right \}}$
$S_{1}$ ${\ displaystyle S_ {1}}$ $S_1$	$\left\{S_{2}\right\}$ ${\ displaystyle \ left \ {S_ {2} \ right \}}$ ${\ displaystyle \ left \ {S_ {2} \ right \}}$	$\left\{S_{1}\right\}$ ${\ displaystyle \ left \ {S_ {1} \ right \}}$ ${\ displaystyle \ left \ {S_ {1} \ right \}}$	$\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$
$S_{2}$ ${\ displaystyle S_ {2}}$ $S_2$	$\left\{S_{1}\right\}$ ${\ displaystyle \ left \ {S_ {1} \ right \}}$ ${\ displaystyle \ left \ {S_ {1} \ right \}}$	$\left\{S_{2}\right\}$ ${\ displaystyle \ left \ {S_ {2} \ right \}}$ ${\ displaystyle \ left \ {S_ {2} \ right \}}$	$\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$
$S_{3}$ ${\ displaystyle S_ {3}}$ $S_ {3}$	$\left\{S_{3}\right\}$ ${\ displaystyle \ left \ {S_ {3} \ right \}}$ ${\ displaystyle \ left \ {S_ {3} \ right \}}$	$\left\{S_{4}\right\}$ ${\ displaystyle \ left \ {S_ {4} \ right \}}$ ${\ displaystyle \ left \ {S_ {4} \ right \}}$	$\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$
$S_{4}$ ${\ displaystyle S_ {4}}$ $S_ {4}$	$\left\{S_{4}\right\}$ ${\ displaystyle \ left \ {S_ {4} \ right \}}$ ${\ displaystyle \ left \ {S_ {4} \ right \}}$	$\left\{S_{3}\right\}$ ${\ displaystyle \ left \ {S_ {3} \ right \}}$ ${\ displaystyle \ left \ {S_ {3} \ right \}}$	$\emptyset$ ${\ displaystyle \ emptyset}$ $\ emptyset$

Automat cu stare finită al exemplului

De asemenea, este important să rețineți că $LA$ ${\ displaystyle A}$ $LA$ poate fi obținut din unirea a două automate finite deterministe ale căror stări sunt respectiv $\left\{S_{1},S_{2}\right\}$ ${\ displaystyle \ left \ {S_ {1}, S_ {2} \ right \}}$ ${\ displaystyle \ left \ {S_ {1}, S_ {2} \ right \}}$ Și $\left\{S_{3},S_{4}\right\}$ ${\ displaystyle \ left \ {S_ {3}, S_ {4} \ right \}}$ ${\ displaystyle \ left \ {S_ {3}, S_ {4} \ right \}}$ . Limbajul regulat recunoscut de automat este de asemenea exprimabil prin expresie regulată

$(1^{*}(01^{*}01^{*})^{*})+(0^{*}(10^{*}10^{*})^{*})$ ${\ displaystyle (1 ^ {*} (01 ^ {*} 01 ^ {*}) ^ {*}) + (0 ^ {*} (10 ^ {*} 10 ^ {*}) ^ {*}) }$ ${\ displaystyle (1 ^ {*} (01 ^ {*} 01 ^ {*}) ^ {*}) + (0 ^ {*} (10 ^ {*} 10 ^ {*}) ^ {*}) }$

Bibliografie

(EN) automat finit nedeterministic, în Academic Press Dictionary of Science and Technology, Oxford, Elsevier Science & Technology, 1992.
(EN) teoria automatelor , în Encyclopedia of Computer Science, Hoboken, Wiley, 2003.
( EN ) John E. Hopcroft , Rajeev Motwani; Jeffrey D. Ullman , Automate finite , în Introducere în teoria automatelor, limbaje și calcul , Addison Wesley, 15 iulie 2006, ISBN 978-0-321-46225-1 .
(EN) Martin Davis , Ron Sigal; Elaine J. Weyuker, Automate finite , în Computabilitate, Complexitate și Limbi: Fundamente ale științei teoretice a computerelor , Morgan Kaufmann, 17 februarie 1994, ISBN 978-0-12-206382-4 .

Elemente conexe

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe automatele cu stări finite nedeterministe

Teoria automatelor : limbaje formale și gramatici formale
Ierarhia Chomsky	Gramatica formală	Limba	Automat minim
Tipul-0	(nelimitat)	Recursiv enumerabil	Mașină Turing
	(nelimitat)	Recursiv	Decider
Tipul 1	Context dependent	Context dependent	Automat liniar
Tipul 2	Fără context	Fără context	Automat cu baterie ND
Tipul 3	Regulat	Regulat	Stări finite
Fiecare categorie de limbă sau gramatică este un subset adecvat al categoriei imediat deasupra acesteia.

Portal IT : accesați intrările Wikipedia care se ocupă cu IT