Mașină de stări deterministă

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 24 iunie 2022; verificările necesită 3 modificări .

Un automat finit determinist ( DFA , DFA , eng. deterministic finite automaton , DFSA , eng. deterministic finite-state automaton , DFSM eng. deterministic finite-state machine ), cunoscut și ca un determinist finite recognocer , este un automat finit care acceptă sau respinge un șir de caractere dat prin trecerea prin succesiunea de stări definită de șirul [1] . Are o singură secvență de stări în timpul funcționării. McCulloch și Walter Pitts au fost printre primii cercetători care au propus un concept asemănător mașinii de stat în 1943 [2] [3] .

Figura ilustrează o mașină cu stări finite deterministă folosind o diagramă de stări . În acest exemplu, există trei stări - S 0 , S 1 și S 2 (reflectate în figură prin cercuri). Automatul acceptă o secvență finită de zerouri și unu ca intrare. Pentru fiecare stare, există o săgeată de tranziție care duce de la o stare la alta atât pentru 0, cât și pentru 1. După citirea unui simbol, DFA trece determinist de la o stare la alta, urmând săgeata de tranziție. De exemplu, dacă automatul este în starea S 0 și simbolul de intrare este 1, atunci automatul trece în mod determinist la starea S 1 . Un DFA are o stare inițială (reprezentată grafic printr-o săgeată din neant) de unde începe calculul și un set de stări finale (reprezentate grafic ca un cerc dublu) care determină dacă calculul are succes.

DFA este definit ca un concept matematic abstract, dar este adesea implementat în hardware și software pentru a rezolva probleme specifice. De exemplu, un DFA poate modela programe care decid dacă o adresă de e- mail introdusă de utilizator este validă.

DFA recunoaște exact o varietate de limbaje obișnuite [1] care sunt utile pentru analiza lexicală și potrivirea modelelor , printre altele . DFA-urile pot fi construite din automate finite nedeterministe ( NFA ) prin reducerea DFA-urilor la NFA .

Definiție formală

Un automat finit determinist este un tuplu de 5 format din $M$ $(Q,\Sigma,\delta,q_{0},F)$

set finit de stări $Q$
un set finit de caractere de intrare, numit alfabet $\Sigma$
funcția de tranziție $\delta :Q\times \Sigma \rightarrow Q$
stare initiala $q_{0}\in Q$
set de stări finale $F\subseteq Q$

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

$r_{0}=q_{0}$
$r_{i+1}=\delta (r_{i},a_{i+1})$ , pentru $i=0,...,n-1$
$r_{n}\în F$ .

Cu alte cuvinte, prima condiție spune că mașina pornește din starea . A doua condiție spune că pentru un anumit șir de caractere, mașina trece de la stare la stare conform funcției de tranziție . Ultima condiție spune că mașina acceptă dacă ultimul caracter de intrare al șirului face ca mașina să treacă la una dintre stările finale. În caz contrar, se spune că automatul respinge șirul. Setul de șiruri care acceptă este un limbaj recunoscut de automat , iar acest limbaj este notat cu . $q_{0}$ $w$ $\delta$ $w$ $w$ $M$ $M$ $L(M)$

O mașină cu stări finite deterministă fără stări finale și fără stare inițială este cunoscută ca sistem de tranziție sau semiautomat .

Pentru o definiție formală mai completă, consultați articolul „ Teoria automatelor ”.

Automate complete și incomplete

Conform definiției de mai sus, automatele finite deterministe sunt întotdeauna complete - ele definesc o tranziție pentru fiecare stare și pentru fiecare simbol de intrare.

În timp ce definiția folosită este cea mai general acceptată, unii autori folosesc termenul de automat finit determinist pentru un concept ușor diferit - un automat care definește cel mult o tranziție (nu exact una ca în definiția de mai sus) pentru fiecare stare și fiecare simbol de intrare. . Funcția de tranziție poate fi parțial definită . Dacă tranziția nu este definită, mașina se oprește.

Exemplu

Următorul exemplu este un DFA binar care necesită ca intrarea să conțină un număr par de zerouri. $M$

$M=(Q,\Sigma,\delta,q_{0},F)$ Unde

$Q=\{S_{1},S_{2}\}$
$\Sigma =\{0,1\}$
$q_{0}=S_{1)$
$F=\{S_{1}\}$ și
$\delta$ definit de următorul tabel de salt :

	0	unu
S1 _	S2 _	S1 _
S2 _	S1 _	S2 _

Starea finală corespunde unui număr par de zerouri în șirul de intrare, în timp ce vorbește despre un număr impar. 1 din fluxul de intrare nu modifică starea automatului. Când șirul de intrare se termină, starea finală va indica dacă șirul de intrare conținea un număr par de zerouri sau nu. Dacă șirul de intrare conține un număr par de zerouri, se va termina în starea finală , deci șirul de intrare va fi acceptat. $S_{1}$ $S_{2}$ $M$ $S_{1}$

Limbajul recunoscut este un limbaj regulat definit printr-o expresie regulată , unde este o stea Kleene , de exemplu, însemnând orice număr (posibil zero) de 1 consecutivi. $M$ ((1*) 0 (1*) 0 (1*))**1*

Proprietăți de închidere

Dacă DFA recunoaște limbile care sunt obținute prin aplicarea unei operațiuni limbilor recunoscute de DFA, atunci DFA se spune că este închis în cadrul operațiunii. DFA sunt închise în urma următoarelor operațiuni.

O asociere
Intersecția [4] (vezi figura)
Concatenare
Plus
Închidere Kleene
Recurs
Repetare
Diferență
Substituţie
Omomorfism

Pentru fiecare operație, construcția optimă, ținând cont de numărul de stări, este determinată în studiul complexității poziționale .

Deoarece DFA sunt echivalente cu automate finite nondeterministe (NFAs ) , aceste închideri pot fi dovedite folosind proprietățile de închidere NFA.

Ca monoid al tranzițiilor

Funcționarea unui DFA dat poate fi privită ca o succesiune de suprapuneri ale unei formulări foarte generale a funcțiilor de tranziție pe sine. Vom construi o astfel de funcție aici.

Pentru un simbol de intrare dat , puteți construi o funcție de tranziție definind pentru toate . (Această tehnică se numește curry .) În această perspectivă , „acționează” asupra stării Q pentru a produce o altă stare. Se poate considera rezultatul unei suprapuneri de funcții , aplicat succesiv la diferite funcții și așa mai departe. Având în vedere o pereche de litere , se poate defini o nouă funcție , unde denotă o suprapunere de funcții. $a\in\Sigma$ $\delta _{a}:Q\rightarrow Q$ $\delta _{a}(q)=\delta (q,a)$ $q\in Q$ $\delta _{a}$ $\delta _{a}$ $\delta _{b)$ $a,b\in \Sigma$ ${\widehat {\delta }}_{ab}=\delta _{a}\circ \delta _{b}$ $\circ$

Este clar că acest proces poate fi continuat recursiv, dând următoarea definiție recursivă : ${\widehat {\delta }}:Q\times \Sigma ^{\star }\rightarrow Q$

{\widehat {\delta }}(q,\epsilon )=q

, unde este șirul gol și

\epsilon

{\widehat {\delta }}(q,wa)=\delta ({\widehat {\delta }}(q,w),a)

, unde și .

w\in \Sigma ^{*},a\in \Sigma

q\in Q

Funcția este definită pentru toate cuvintele . Lucrarea DFA este o succesiune de suprapuneri asupra ei înșiși. ${\widehat {\delta ))$ $w\in \Sigma ^{*}$ ${\widehat {\delta ))$

Repetarea suprapunerilor de funcții formează un monoid . Pentru funcțiile de tranziție, acest monoid este cunoscut ca monoidul de tranziție , sau, uneori, ca semigrupul de transformare . Construcția poate fi inversată - dacă este dat , se poate reconstrui , astfel încât cele două descrieri sunt echivalente. ${\widehat {\delta ))$ $\delta$

Automate locale

Un automat local este un DFA pentru care toate arcurile cu aceeași etichetă duc la același vârf. Automatele locale acceptă clasa limbilor formale , pentru care apartenența unui cuvânt la o limbă este determinată de o „fereastră glisante” de lungimea doi pe cuvânt [5] [6]

Graficul Myhill peste alfabetul A este un grafic direcționat cu setul de vârfuri A și un subset de vârfuri etichetat „inițial” și „terminal”. Limbajul acceptat de graficul Myhill este setul de căi direcționate de la vârful de început până la vârful final - graficul funcționează apoi ca un automat [5] . Clasa limbilor percepute de graficele Myhill este clasa limbilor locale [7] .

Stochastică în DFA

Când starea de început și stările de sfârșit sunt ignorate, un DFA cu stări și un alfabet de dimensiune poate fi considerat ca un digraf de vârf în care toate vârfurile au etichetate arce de ieșire (digraf de rezultat ). Se știe că atunci când este un număr întreg fix, cu o probabilitate mare cea mai mare componentă puternic conectată ( SCC), în care digraful cu rezultate este ales uniform aleatoriu, are o dimensiune liniară și poate fi atinsă de la orice vârf [8] . S-a dovedit, de asemenea, că pe măsură ce , crește cu , întregul digraf are o tranziție de fază la o conexiune puternică, similar modelului Erdős-Rényi pentru conectivitate [9] . $n$ $k$ $n$ $k$ $1,\ldots ,k$ $k$ $k\geqslant 2$ $k$ $k$ $n$

Într-un DFA aleator, numărul maxim de vârfuri atinse de la un vârf cu probabilitate mare este foarte apropiat de numărul de vârfuri din cea mai mare componentă puternic conectată [8] [10] . Acest lucru este valabil și pentru cel mai mare subgraf generat cu unul minim în grad, care poate fi considerat ca o versiune direcționată a -kernel -ului [9] . $unu$

Avantaje și dezavantaje

DFA este unul dintre cele mai practice modele de calcul, deoarece există un algoritm online trivial timp liniar și memorie constantă pentru simularea DFA pe fluxul de intrare. Există, de asemenea, algoritmi eficienți de căutare a recunoașterii DFA:

completarea limbii recunoscute de DFA dat.
unire/intersecție de limbi recunoscute de două DFA date.

Deoarece DFA-urile pot fi reduse la o formă canonică ( DFA minime ), există, de asemenea, doi algoritmi eficienți pentru determinarea

dacă DFA acceptă orice șir (sarcină de testare goală)
dacă DFA acceptă toate rândurile (problema testului de universalitate)
dacă două DFA acceptă aceeași limbă (Problemă de testare a echivalenței)
dacă o limbă recunoscută de un DFA este conținută într-o limbă recunoscută de un alt DFA (sarcină de verificare a includerii)
DFA cu un număr minim de state pentru o anumită limbă obișnuită (problema de minimizare)

DFA-urile sunt echivalente din punct de vedere computațional cu automatele finite nedeterministe (NFA, automate finite nondeterministe , NFA). Acest lucru se datorează faptului că, în primul rând, orice DFA este, de asemenea, un NFA, deci un NFA poate face orice poate face un DFA. De asemenea, având în vedere un NFA, prin reducerea unui DFA la un NFA se poate construi un DFA care recunoaște același limbaj ca și NFA, deși un DFA poate avea exponențial mai multe stări decât un NFA [11] [12] . Cu toate acestea, chiar dacă NFA sunt echivalente din punct de vedere computațional cu DFA, problemele de mai sus nu sunt neapărat rezolvate eficient pentru NFA. Problema de nonuniversalitate pentru un NFA are complexitatea PSPACE , deoarece există NFA mici cu cuvinte de cea mai mică dimensiune exponențială de respins. Un DFA este universal dacă și numai dacă toate stările sunt finite, dar acest lucru nu este adevărat pentru un NFA. Problemele de echivalență, includere și minimizare au și complexitate PSPACE , deoarece necesită formarea complementului NFA, ceea ce duce la o explozie de dimensiune exponențială [13] .

Pe de altă parte, mașinile de stat sunt sever limitate în limbile pe care le recunosc. Multe limbaje simple, inclusiv orice problemă care necesită mai mult decât memorie constantă pentru rezolvare, nu pot fi recunoscute de DFA. Un exemplu clasic de limbaj simplu pe care niciun DFA nu îl poate recunoaște este parantezele sau limbajul Dyck , adică un limbaj care constă din paranteze distanțate corespunzător, ca în cuvântul „(()())”. Este clar intuitiv că niciun DFA nu poate recunoaște limbajul lui Dyck, deoarece DFA-urile nu pot face calcule - automatele precum DFA-urile au nevoie de o stare care să reprezinte orice număr posibil de paranteze „deschise”, ceea ce înseamnă că trebuie să aibă un număr nelimitat de stări. Un alt exemplu simplu este un limbaj format din șiruri de forma pentru un număr finit, dar arbitrar de mare de litere a urmat de un număr egal de litere b [14] . $a^{n}b^{n)$

Vezi și

Automat finit aciclic determinist
Minimizarea DFA
Logica monadică de ordinul doi
Reducerea NFA la DFA
Mașină cuantică de stat
Mașini Turing cu cap de citire care se mișcă spre dreapta
Problemă de separare a cuvintelor
mașină Turing
Mașină finită deterministă bidirecțională

Note

↑ 1 2 Hopcroft, Motwani, Ullman, 2001 .
↑ McCulloch, Pitts, 1943 .
↑ Rabin, Scott, 1959 .
↑ Hopcroft, Ullman, 1979 , p. 59-60.
↑ 12 Lawson , 2004 , p. 129.
↑ Sakarovici, 2009 , p. 228.
↑ Lawson, 2004 , p. 128.
↑ 1 2 Grusho, 1973 , p. 633–637.
↑ 1 2 Cai, Devroye, 2017 , p. 428–458.
↑ Carayol, Nicaud, 2012 , p. 194–205.
↑ Sakarovici, 2009 , p. 105.
↑ Lawson, 2004 , p. 63.
↑ Startseite - Lehrstuhl für Theoretische Informatik . Preluat la 6 februarie 2020. Arhivat din original la 8 august 2018. (nedefinit)
↑ Lawson, 2004 , p. 46.

Literatură

John Hopcroft , Rajeev Motwani , Jeffrey Ullman . Introducere în teoria automatelor, limbaje și calcul . - 2. - Addison Wesley , 2001. - ISBN 0-201-44124-1 .
Mark V. Lawson. Automat finit. - Chapman și Hall/CRC, 2004. - ISBN 1-58488-255-7 .
McCulloch W.S., Pitts W. Un calcul logic al ideilor immanente în activitatea nervoasă // Buletin de biofizică matematică. - 1943. - V. 5 , nr. 4 . — S. 115–133 . - doi : 10.1007/BF02478259 . Arhivat din original pe 12 aprilie 2019.
Rabin MO, Scott D. Automate finite și problemele lor de decizie. // IBM J. Res. dev. - 1959. - T. 3 , nr. 2 . — S. 114–125 . - doi : 10.1147/rd.32.0114 .
Jacques Sakarovitch. Elemente de teoria automatelor / Tradus din franceză de Reuben Thomas. - Cambridge: Cambridge University Press , 2009. - ISBN 978-0-521-84425-3 .
Michael Sipser. Introducere în teoria calculului . - Boston: PWS, 1997. - ISBN 0-534-94728-X . Secțiunea 1.1: Automate finite, pp. 31-47. Subsecțiunea „Probleme determinabile privind limbile obișnuite” din secțiunea 4.1: Limbi determinabile, pp. 152-155.4.4 DFA poate accepta numai limbajul obișnuit
John E. Hopcroft, Jeffrey D. Ullman. Introducere în teoria automatelor, limbaje și calcul . - Reading/MA: Addison-Wesley, 1979. - ISBN 0-201-02988-X .
- Tradus de John Hopcroft, Rajiv Motwani, Geoffrey Ullman. Introducere în teoria automatelor, limbajelor și calculelor. - Moscova, Sankt Petersburg, Kiev: Williams, 2002. - ISBN 5-8459-0261-4 .
Grusho A. A. Despre distribuțiile limită ale unor caracteristici ale graficelor automate aleatoare // Matem. note. - 1973. - T. 4 . - P. 133-141, 633-637. - doi : 10.1007/BF01095785 .
Xing Shi Cai, Luc Devroye. Structura grafică a unui automat determinist ales la întâmplare // Random Structures & Algorithms. - 2017. - Octombrie ( vol. 51 , numărul 3 ). - doi : 10.1002/rsa.20707 .
Arnaud Carayol, Cyril Nicaud. Distribuția numărului de stări accesibile într-un automat determinist aleatoriu // STACS'12 (29th Symposium on Theoretical Aspects of Computer Science) . - Paris, Franța, 2012. - T. 14.

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