Mașină de stări nedeterministă

Un automat finit nedeterminist (NFA, eng. nondeterministic finite automaton , NFA) este un automat determinist finit (DFA, eng. deterministic finite automaton , DFA) care nu îndeplinește următoarele condiții:

oricare dintre tranzițiile sale este determinată în mod unic de starea curentă și de simbolul de intrare
citirea unui caracter de intrare este necesară pentru fiecare schimbare de stare.

În special, orice DFA este, de asemenea, un NFA.

Folosind algoritmul de construcție a subsetului , orice NFA poate fi convertit într-un DFA echivalent, adică un DFA care recunoaște același limbaj formal [1] . La fel ca DFA, NFA recunoaște numai limbile obișnuite .

NFA a fost propus în 1959 de Michael O. Rabin și Dana Scott [2] care au arătat că este echivalent cu DFA. NFA este folosit în implementarea expresiilor regulate - construcția lui Thompson este un algoritm pentru conversia unei expresii regulate în NFA care poate recunoaște eficient modelul șirurilor. Dimpotrivă, algoritmul lui Kleene poate fi folosit pentru a transforma un NFA într-o expresie regulată a cărei dimensiune depinde, în general, exponențial de dimensiunea automatului.

NFA este generalizat în multe feluri, de exemplu: automate finite nedeterministe cu tranziții ε , traductoare cu stări finite, automate pushdown, automate alternante, ω-automate și automate probabilistice . Pe lângă DFA, sunt cunoscute și alte cazuri speciale de NFA - unambiguous finite automata ( eng. unambiguous finite automata , UFA) și auto -verifying finite automata ( eng. self-verifying finite automata , SVFA).

Introducere informală

Există mai multe descrieri echivalente informale:

Un NFA, ca un DFA , primește un șir de caractere de intrare. Pentru fiecare simbol de intrare, acesta trece la o stare nouă până când a procesat toate simbolurile de intrare. La fiecare pas, automatul alege aleatoriu una dintre posibilele tranziții. Dacă există o „trecere de speranță”, adică o secvență de alegeri care duc la o stare finală după ce șirul de intrare a fost preluat complet, atunci șirul este acceptat. Dacă nu există o secvență care, după procesarea întregului șir de intrare [3] , aduce automatul în starea finală, atunci șirul de intrare este respins [4] [5] .
Lăsați NFA să ia din nou un șir de caractere de intrare, un caracter după altul. La fiecare pas în care două sau mai multe tranziții se dovedesc a fi valide, automatul se „clonează” în numărul necesar de copii, fiecare dintre acestea făcând tranziții diferite. Dacă nu se poate face nicio tranziție, copia curentă este o fundătură și moare. Dacă, după preluarea tuturor caracterelor din șirul de intrare, oricare dintre copii trece în starea finală, șirul de intrare este acceptat, în caz contrar este respins [6] [7] [8] .

Definiție formală

Pentru o introducere mai elementară în definiția formală, consultați articolul „ Teoria automatelor ”.

Automate

Un NFA este reprezentat oficial ca un tuplu de 5, format din: $(Q,\Sigma,\Delta,q_{0},F)$

set finit de stări . $Q$
set finit de simboluri de intrare . $\Sigma$
functii de tranzitie : . $\Delta$ $Q\times \Sigma \rightarrow P(Q)$
starea initiala . $q_{0}\in Q$
seturi de state recunoscute ca state finale . $F$ $F\subseteq Q$

Aici înseamnă gradul setului . $P(Q)$ $Q$

Limba recunoscută

Având în vedere un NFA , recunoaște un limbaj care este notat și definit ca un set de șiruri de caractere peste alfabetul acceptat de automat . $M=(Q,\Sigma,\Delta,q_{0},F)$ $L(M)$ $\Sigma$ $M$

În termeni generali, conform explicațiilor informale de mai sus , există mai multe definiții formale echivalente ale șirurilor acceptate de automat : $w=a_{1}a_{2}...a_{n)$ $M$

$w$ este acceptată dacă există o succesiune de stări în aşa fel încât $r_{0},r_{1},...,r_{n)$ $Q$
1. $r_{0}=q_{0}$
2. $r_{i+1}\in \Delta (r_{i},a_{i+1})$ , pentru $i=0,\ldots ,n-1$
3. $r_{n}\în F$ .

Cuvinte. Prima condiție spune că mașina pornește de la starea . A doua condiție spune că pentru fiecare caracter din șir , mașina trece de la stare la stare conform funcției de tranziție . Ultima condiție spune că mașina acceptă un șir dacă șirul de intrare face ca mașina să se termine în starea sa finală. Pentru ca un șir să fie acceptat de un automat , nu este necesar ca orice succesiune de stări să se termine într-o stare finală, este suficient ca o secvență să conducă la o astfel de stare. În caz contrar, adică dacă este imposibil să treci de la la starea din , după , se spune că automatul respinge șirul. Setul de șiruri pe care le acceptă automatul este un limbaj recunoscut de automat , iar acest limbaj este notat ca [9] [10] .

q_{0}

w

\Delta

w

w

w

M

q_{0}

F

w

M

M

L(M)

Alternativ, este acceptat dacă , unde este definit recursiv : $w$ $\Delta ^{*}(q_{0},w)\cap F\not =\emptyset$ $\Delta ^{*}:Q\times \Sigma ^{*}\rightarrow P(Q)$
1. $\Delta ^{*}(r,\epsilon )=\{r\)$ , unde este șirul gol $\epsilon$
2. $\Delta ^{*}(r,xa)=\bigcup _{r'\in \Delta ^{*}(r,x)}\Delta (r',a)$ pentru orice . $x\in \Sigma ^{*},a\in \Sigma$

Cu alte cuvinte, este setul tuturor stărilor accesibile din starea la obținerea șirului . Un șir este acceptat dacă o stare finală de la poate fi atinsă din starea de început pentru șirul de intrare [11] [12] .

\Delta ^{*}(r,x)

r

X

w

F

q_{0}

w

Stare inițială

Definiția automatului de mai sus folosește o singură stare inițială , care nu este o cerință. Uneori, un NFA este definit cu un set de stări inițiale. Există o construcție simplă care duce un NFA cu mai multe stări inițiale la un NFA cu o singură stare inițială.

Exemplu

Următorul automat alfabet binar determină dacă șirul de intrare se termină într-unul. Fie , unde funcția de tranziție poate fi definită de următorul tabel de tranziție de stări (comparați cu figura de sus din stânga): $M$ $M=(\{p,q\},\{0,1\},\Delta,p,\{q\})$ $\Delta$

IntrareStat	0	unu
$p$	$\{p\}$	$\{p,q\)$
$q$	$\emptyset$	$\emptyset$

Deoarece mulțimea conține mai multe stări, automatul este nedeterminist. Limbajul automatului poate fi descris ca un limbaj regulat dat de o expresie regulată . $\Delta(p,1)$ $M$ $M$ (0|1)*1

Toate secvențele de stări posibile pentru șirul de intrare „1011” sunt prezentate în figura de mai jos. Șirul este acceptat de automat deoarece una dintre secvențele de stări satisface definiția de mai sus. Nu contează că celelalte secvențe nu reușesc. Desenul poate fi interpretat în două moduri: $M$

În ceea ce privește explicația „lucky run” de mai sus , fiecare cale din figură reprezintă o secvență de alegeri . $M$
Pentru a explica din punct de vedere al „clonării”, fiecare coloană verticală arată toate clonele automatului la un moment dat, mai multe săgeți care ies dintr-un nod înseamnă clonare, un nod fără săgeți de ieșire înseamnă „moartea” clonei. $M$

Abilitatea de a citi aceeași figură în două moduri arată, de asemenea, echivalența celor două explicații de mai sus.

Dacă luăm în considerare prima dintre definițiile formale de mai sus , șirul „1011” este acceptat, deoarece atunci când este citit , poate trece o succesiune de stări care îndeplinește condițiile 1-3. $M$ $\langle r_{0},r_{1},r_{2},r_{3},r_{4}\rangle =\langle p,p,p,p,q\rangle$
Dacă luăm în considerare a doua dintre definițiile formale, pasajul de jos în sus arată că , prin urmare, , și apoi , de unde , și, în sfârșit, . Deoarece acest set conține , șirul „1011” este acceptat. $\Delta ^{*}(p,\epsilon )=\{p\}$ $\Delta ^{*}(p,1)=\Delta (p,1)=\{p,q\)$ $\Delta ^{*}(p,10)=\Delta (p,0)\cup \Delta (q,0)=\{p\}\cup \{\)$ $\Delta ^{*}(p,101)=\Delta (p,1)=\{p,q\)$ $\Delta ^{*}(p,1011)=\Delta (p,1)\cup \Delta (q,1)=\{p,q\}\cup \{\)$ $\{q\}$

În schimb, șirul „10” este respins de automat (toate secvențele posibile de stări pentru șirul de intrare pentru o anumită intrare sunt prezentate în figura din dreapta sus), deoarece nu există o cale care să ajungă la starea finală după citirea finalului caracterul 0. Deși starea poate fi atinsă după primirea primului caracter „1” nu înseamnă că șirul de intrare „10” este acceptabil. Înseamnă doar că șirul de intrare „1” ar fi acceptabil. $M$ $q$ $q$

Echivalență DFA

Un automat finit determinist ( DFA ) poate fi considerat ca un tip special de NFA în care pentru orice stare și litere ale alfabetului, funcția de tranziție are o singură stare rezultată. Astfel, este clar că orice limbaj formal care poate fi recunoscut cu un DFA poate fi recunoscut și cu un NFA.

În schimb, pentru orice NFA există un DFA care recunoaște același limbaj formal. Un DFA poate fi construit folosind construcția subsetului .

Acest rezultat arată că NFA, în ciuda flexibilității sale mari, nu poate recunoaște limbile care nu pot fi recunoscute de niciun DFA. Acest lucru este, de asemenea, important în practică, pentru a converti NFA mai simple din punct de vedere structural în DFA mai eficiente din punct de vedere computațional. Cu toate acestea, dacă NFA are n stări, DFA rezultat poate avea până la 2n stări, ceea ce face uneori construcția nepractică pentru NFA mari.

NCA cu ε-tranziții

Automatul finit nedeterminist cu ε-tranziții (NFA-ε) este deja o generalizare suplimentară pentru NFA. Acest automat cu funcție de tranziție are dreptul să aibă șirul gol ε ca intrare. O tranziție fără a utiliza un simbol de intrare se numește tranziție ε. Într-o diagramă de stări, aceste tranziții sunt de obicei etichetate cu litera greacă ε. ε-tranzițiile oferă o modalitate convenabilă de modelare a sistemelor a căror stare actuală nu este cunoscută cu exactitate. De exemplu, dacă modelăm un sistem a cărui stare curentă nu este clară (după procesarea unui șir de intrare) și poate fi q sau q', putem adăuga o tranziție ε între aceste două stări, aducând automatul la ambele stări la acelasi timp.

Definiție formală

NFA-ε este reprezentat formal printr -un tuplu de 5 , , care constă din: $(Q,\Sigma,\Delta,q_{0},F)$

set finit de stări $Q$
un set finit de caractere de intrare , numit alfabet $\Sigma$
funcții de tranziție $\Delta:Q\times (\Sigma \cup \{\epsilon \})\rightarrow P(Q)$
starea inițială (sau de pornire ). $q_{0}\in Q$
un set de stări care sunt considerate stări valide (sau finale ) . $F$ $F\subseteq Q$

Aici înseamnă puterea mulțimii , iar ε înseamnă șirul gol. $P(Q)$ $Q$

ε-Închiderea unei stări sau a unui set de stări

Pentru o stare, notăm setul de stări accesibile din următoarele ε-tranziții în funcțiile de tranziție , și anume, dacă există o succesiune de stări astfel încât: $q\in Q$ $E(q)$ $q$ $\Delta$ $p\in E(q)$ $q_{1},...,q_{k)$

$q_{1}=q$ ,
$q_{i+1}\in \Delta (q_{i},\epsilon )$ pentru orice $1\leqslant i<k$
$q_{k}=p$ .

Mulțimea este cunoscută ca închiderea stării ε . $E(q)$ $q$

Închiderea ε este definită și pentru setul de stări. Închiderea ε a mulțimii de stări, , a automatului NK este definită ca mulțimea de stări la care se poate ajunge din elementele mulțimii prin ε-tranziții. Formal, pentru $P$ $P$ $P\subseteq QE(P)=\cup _{q\in P}E(q)$

Stări acceptabile

Să fie un șir peste alfabet . Automatul acceptă un șir dacă există o secvență de stări în următoarele condiții: $w=a_{1}a_{2}...a_{n)$ $\Sigma$ $M$ $w$ $r_{0},r_{1},...,r_{n)$ $Q$

$r_{0}\in E(q_{0})$
$r_{i+1}\in E(r')$ , unde pentru orice $r'\in \Delta (r_{i},a_{i+1})$ $i=0,...,n-1$
$r_{n}\în F$ .

Cuvinte. Prima condiție spune că mașina pornește dintr-o stare care este accesibilă din stare prin tranziții ε. A doua condiție spune că după citirea , mașina selectează tranziția de la la și apoi efectuează orice număr de ε-tranziții în funcție de tranziția de la la . Ultima condiție spune că mașina acceptă dacă ultimul caracter introdus face ca mașina să treacă la una dintre stările acceptate. În caz contrar, se spune că automatul respinge șirul. Setul de șiruri de caractere pe care îl acceptă este limbajul pe care îl recunoaște automatul și acest limbaj este notat ca .

q_{0}

a_{i}

\Delta

r_{i}

r'

\Delta

r'

r_{i+1}

w

M

M

L(M)

Exemplu

Să existe un NFA-ε cu un alfabet binar care determină dacă șirul de intrare conține un număr par de zerouri sau un număr par de unu. Rețineți că 0 apariții este un număr par. $M$

În notație formală, fie , unde relația de tranziție poate fi definită printr- un astfel de tabel de tranziție de stări : $M=(\{S_{0},S_{1},S_{2},S_{3},S_{4}\},\{0,1\},\Delta ,S_{0} ,\{S_{1},S_{3}\})$ $\Delta$

IntrareStat	0	unu	ε
S0 _	{}	{}	{ S 1 , S 3 }
S1 _	{ S2 } _	{ S 1 }	{}
S2 _	{ S 1 }	{ S2 } _	{}
S3 _	{ S 3 }	{ S4 } _	{}
S4 _	{ S4 } _	{ S 3 }	{}

$M$ poate fi gândit ca unirea a două DFA , unul cu state și celălalt cu state . Limbajul poate fi descris ca un limbaj regulat dat de expresia regulată (1*(01*01*)*) ∪ (0*(10*10*)*). Definim folosind ε-tranziții, dar putem defini fără ele. $\{S_{1},S_{2}\}$ $\{S_{3},S_{4}\}$ $M$ $M$ $M$

Echivalența NFA-urilor

Pentru a arăta că NFA-ε este echivalent cu NFA, mai întâi rețineți că NFA este un caz special de NFA-ε, rămâne să arătăm că pentru orice NFA-ε există un NFA echivalent.

Să fie NFA-ε. NFA este echivalent cu , unde pentru orice și . $A=(Q,\Sigma,\Delta,q_{0},F)$ $A'=(Q,\Sigma,\Delta ',E(q_{0}),F)$ $A$ $a\in\Sigma$ $q\in Q$ $\Delta '(q,a)=E(\Delta (q,a))$

Atunci NFA-ε este echivalent cu NFA. Deoarece NFA este echivalent cu DFA, NFA-ε este, de asemenea, echivalent cu DFA.

Proprietăți de închidere

Se spune că un NFA este închis sub o operație ( binară / unară ). Dacă NFA recunoaște limbile care sunt obținute prin aplicarea acestei operațiuni la limbile recunoscute de NFA. ANF-urile sunt închise pentru următoarele operațiuni.

Fuzionarea (vezi imaginea)
intersecție
Concatenare
Plus
Închidere Kleene

Deoarece NFA-urile sunt echivalente cu automatele finite nedeterministe de tranziție ε (NFA-ε), închiderile de mai sus sunt dovedite folosind proprietățile de închidere ale NFA-ε. Din proprietățile de închidere de mai sus rezultă că NFA-urile recunosc numai limbaje obișnuite .

NFA-urile pot fi construite din orice expresie regulată folosind algoritmul Thompson .

Proprietăți

Mașina pornește dintr-o anumită stare inițială și citește un șir de caractere format din literele alfabetului său . Automatul folosește funcția de tranziție Δ pentru a determina următoarea stare din starea curentă și caracterul sau șirul gol tocmai citit. Cu toate acestea, „următoarea stare a NFA depinde nu numai de simbolul de intrare curent, ci și de un număr arbitrar de evenimente de intrare ulterioare. În timp ce aceste evenimente ulterioare au loc, este imposibil să se determine în ce stare se află mașina” [13] . Dacă automatul este în starea finală după ultimul caracter citit, se spune că NFA acceptă șirul, în caz contrar se spune că respinge șirul.

Setul tuturor șirurilor acceptate de NFA este limba pe care NFA o acceptă. Această limbă este o limbă obișnuită .

Pentru orice NFA, se poate găsi un automat finit determinist (DFA) care acceptă același limbaj. Prin urmare, este posibil să convertiți un NFA existent într-un DFA pentru a implementa o mașină (posibil) mai simplă. O astfel de transformare se realizează folosind construcția subset , care poate duce la o creștere exponențială a numărului de stări necesare. Pentru o dovadă formală a construcției subsetului, consultați articolul „ Construcția subsetului ”.

Implementare

NFA poate fi modelat în unul dintre următoarele moduri:

Convertiți în DFA echivalent. În unele cazuri, acest lucru poate duce la o creștere explozivă a numărului de state [14] .
Menținerea setului tuturor stărilor în care se poate găsi NFA după citirea cuvântului. La procesarea unui simbol de intrare, este necesar să combinați rezultatele funcției de tranziție aplicate setului curent de stări pentru a obține următorul set. Dacă sunt permise ε-tranziții, trebuie să includă și toate stările accesibile prin astfel de tranziții (ε-închidere). Fiecare pas necesită cel mult calcule, unde s este numărul de stări NFA. Automatul acceptă un șir dacă și numai dacă, la procesarea ultimului caracter de intrare, una dintre stările curente este finală. Un șir de lungime n poate fi procesat în timp O (ns 2 ) [15] folosind memoria O ( s ). $s^{2}$

Aplicații NCA

NFA și DFA sunt echivalente în sensul că, dacă o limbă este recunoscută de un NFA de către un automat, este recunoscută și de un DFA. Este adevărat și invers. Stabilirea unei astfel de echivalențe este importantă și utilă. Important pentru că NFA-urile pot fi utilizate pentru a reduce complexitatea lucrării matematice care este necesară pentru a stabili proprietăți importante în teoria algoritmilor . De exemplu, este mult mai ușor să demonstrezi închiderea limbilor obișnuite cu NFA-uri decât cu DFA-uri. Util, deoarece construirea unui NFA pentru a recunoaște limba respectivă este uneori mult mai importantă decât construirea unui DFA pentru acea limbă.

Vezi și

Mașină de stări deterministă
Mașină finită nedeterministă bidirecțională
Automat cu memorie revistă
mașină Turing

Note

↑ Martin, 2010 , p. 108.
↑ Rabin și Scott, 1959 , p. 114–125.
↑ O secvență de alegeri poate duce la un „fund” în care niciuna dintre tranziții nu este valabilă pentru simbolul de intrare curent, iar acest caz este considerat un eșec (șirul este respins).
↑ Hopcroft, Ullman, 1979 , p. 19.
↑ Aho, Hopcroft & Ullman 1974 , p. 319.
↑ Hopcroft, Ullman, 1979 , p. 19-20.
↑ Sipser, 1997 , p. 48.
↑ Hopcroft, Motwani, Ullman, 2001 , p. 56.
↑ Aho, Hopcroft & Ullman 1974 , p. 320.
↑ Sipser, 1997 , p. 54.
↑ Hopcroft, Ullman, 1979 , p. 21.
↑ Hopcroft, Motwani, Ullman, 2001 , p. 59.
↑ Finite-State Machine FOLDOC Dicționar online gratuit de calcul . Data accesului: 11 februarie 2020. Arhivat din original pe 4 aprilie 2015. (nedefinit)
↑ Chris Calabro. NFA la DFA explodează. 27-02-2005 . Consultat la 11 februarie 2020. Arhivat din original pe 7 februarie 2013. (nedefinit)
↑ Hopcroft, Motwani, Ullman, 2001 , p. 153.

Literatură

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman. Proiectarea și analiza algoritmilor de calculator . - Reading/MA: Addison-Wesley, 1974. - ISBN 0-201-00029-6 .
- Aho A., Hopcroft J., Ulman J. Construcția și analiza algoritmilor de calcul. - Moscova: Mir, 1979.
John E. Hopcroft, Jeffrey D. Ullman. Introducere în teoria automatelor, limbaje și calcul . - Reading/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introducere în teoria automatelor, limbaje și calcul . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
- John Hopcroft , Rajiv Motwani, Jeffrey Ullman. Introducere în teoria automatelor, limbaje și calcul. - M . : „Williams” , 2002. - 528 p. - ISBN 0-201-44124-1 .
Michael Sipser. Introducere în teoria calculului . - Boston/MA: PWS Publishing Co., 1997. - ISBN 0-534-94728-X .
Ioan Martin. Introducere în limbaje și teoria calculului. - McGraw Hill, 2010. - ISBN 978-0071289429 .
Rabin MO, Scott D. Automate finite și problemele lor de decizie // Jurnalul IBM de cercetare și dezvoltare. - 1959. - Aprilie ( vol. 3 , numărul 2 ). - doi : 10.1147/rd.32.0114 .
Allan C., Avgustinov P., Christensen AS, Hendren L., Kuzins S., Lhoták O., de Moor O., Sereni D., Sittampalam G., Tibble J. Adding trace matching with free variables to AspectJ // In Actele celei de-a 20-a conferințe anuale ACM SIGPLAN privind programarea orientată pe obiecte, sisteme, limbaje și aplicații . — San Diego, CA, SUA: OOPSLA '05. ACM, New York, NY, 2005. pp. 345-364. Arhivat pe 18 septembrie 2009 la Wayback Machine

Limbi formale și gramatici formale
Concepte generale	Ierarhia Chomsky Alfabet Cuvânt
Tip 0	Gramatică nelimitată mașină Turing limbaj enumerat Limbajul rezolvabil
Tipul 1	Gramatică sensibilă la context Limbaj sensibil la context Automat delimitat liniar
Tipul 2	Gramatică fără context Gramatică ambiguă Limbaj fără context Automat Pushdown ( determinist ) Lema de creștere Lema lui Ogden Teorema lui Cook
Tip 3	Gramatica obișnuită limbaj obișnuit Expresie uzuala Mașină de stări ( deterministă , nedeterministă ) Minimizarea DFA Determinarea NFA Teorema Myhill-Nerode
analizare	Analizor LL Analizor LR Metoda coborârii recursive Algoritmul Kok-Younger-Kasami