Automat finit

Un automat finit (AF) sau o "mașină cu un număr finit de stări" este un model de comportament compus din stări, tranziții și acțiuni. O stare stochează informații despre trecut, adică reflectă schimbările intrării de la inițializarea sistemului până în momentul de față. O tranziție indică o schimbare de stare și este descrisă de o condiție care este nevoie să fie îndeplinită pentru a declanșa tranziția. O acțiune este o descriere a unei activități ce urmează a fi executată la un anumit moment. Există câteva tipuri de acțiuni:

Acțiune de intrare

executată la intrarea într-o stare

Acțiune de ieșire

executată la ieșirea dintr-o stare

Acțiune de intrare de date

acțiune executată în funcție de starea prezentă și de datele de intrare

Acțiune de tranziție

acțiune executată în momentul unei tranziții

AF poate fi reprezentat printr-o diagramă de stări (sau diagramă de stări și tranziții) ca în figura 1. În plus, se folosesc și tabele de tranziție. Cea mai comună reprezentare este dată mai jos: combinația stării curente (B) și condiției (Y) dă starea următoare (C). Informații complete privind acțiunile pot fi adăugate doar ca note de subsol.

În plus față de utilizarea lor în modelarea sistemelor reactive, prezentată aici, automatele finite sunt importante în multe domenii, inclusiv în lingvistică, informatică, filosofie, biologie, matematică, și logică. Mașinile cu stări finite sunt un tip de automate studiate de teoria automatelor. În informatică, automatele finite sunt folosite pe larg în modelarea comportamentului aplicațiilor, proiectarea sistemelor digitale hardware, ingineria software, compilatoare, și în studiul computației și limbajelor.

Se disting două grupuri de automate finite: Acceptoare și Transductoare.

Acest gen de mașină dă o ieșire binară, fie da, fie nu, reprezentând răspunsul la întrebarea "Intrarea este acceptată sau nu de mașină?". Mașina poate fi descrisă și ca definitorie pentru un limbaj, în cazul de față limbajul definit ar conține toate cuvintele acceptate de mașină și nici unul din cele neacceptate. Toate stările automatului se clasifică în stări acceptante (finale) sau neacceptante. Dacă la momentul terminării procesării întregului șir de intrare automatul este într-o stare finală, atunci intrarea este acceptată, altfel nu. Ca o regulă, intrarea este compusă din simboluri (caractere); nu se folosesc acțiunile. Exemplul din figura 2 arată un automat finit care acceptă cuvântul "bine". În acest AF, singura stare finală este starea Succes.

Transductoarele generează ieșire pe baza unei intrări date și/sau a unei stări, folosind acțiuni. Ele sunt folosite în controlul aplicațiilor. Aici se disting două tipuri:

Mașina Moore

Automatul folosește doar acțiuni de intrare, și deci ieșirea depinde doar de stare. Avantajul modelului Moore este simplificarea comportamentului. Exemplul din figura 3 arată automatul Moore care controlează ușa unui ascensor. Mașina de stare recunoaște două comenzi: "cmd_deschide" și "cmd_închide" care declanșează schimbări ale stării. Acțiunea de intrare (I:) în starea "Deschis" pornește un motor care deschide ușa, acțiunea de intrare în starea "Închis" declanșează motorul în direcție opusă, închizând ușa. Stările "Deschis" și "Închis" nu efectuează nici o acțiune. Ele doar semnalizează celor din exterior (eventual altor automate finite) situația curentă: "ușa este deschisă" respectiv "ușa este închisă".

Mașina Mealy

AF folosește doar acțiuni de intrare de date, adică ieșirea depinde de intrare și de starea curentă. Utilizarea unui AF Mealy conduce adesea la o reducere a numărului de stări. Exemplul din figura 4 arată un automat Mealy care implementează același comportament ca și cel din exemplul Moore (comportamentul depinde de modelul de execuție al AF implementat și va funcționa de exemplu pentru AF virtuale, dar nu pentru AF conduse de evenimente). Există două acțiuni (I:): "pornește motorul care închide ușa dacă sosește comanda cmd_închide" și "pornește motorul în direcție opusă pentru a deschide ușa dacă sosește comanda cmd_deschide".

Mai multe detalii despre diferențele dintre modelele Mealy și Moore, precum și despre utilizarea lor, se pot găsi în nota tehnică externă O altă distincție care se face între automatele finite este cea între automatele finite deterministe (AFD) și cele nedeterministe (AFN). În automatele deterministe, din fiecare stare se poate efectua exact o singură tranziție pentru fiecare intrare posibilă. În automatele nedeterministe, pentru o anumită stare și o anumită intrare, pot fi mai multe tranziții posibile, sau chiar nici una. Această distincție este relevantă în practică, dar nu și în teorie, deoarece există un algoritm care poate transforma orice AFN într-un AFD echivalent, deși această transformare mărește, de obicei, complexitatea automatului.

Automatul finit cu o singură stare se numește automat finit combinațional și folosește doar acțiuni de intrare de date. Acest concept este util în cazurile în care este nevoie ca un număr de AF să lucreze împreună, și în cele în care este convenabil ca o parte pur combinațională să fie considerată ca fiind un automat finit pentru unele unelte de proiectare.

Ieșirea și starea următoare a unui automat finit este o funcție de intrare și de starea curentă. Logica unui AF este prezentată în figura 5.

În funcție de tip, există mai multe definiții. Un automat finit acceptor este un cvintuplu ${\displaystyle <\Sigma ,S,s_{0},\delta ,F>}$, unde:

• ${\displaystyle \Sigma }$ este alfabetul de intrare (o mulțime finită și nevidă de simboluri).
• S este o mulțime finită și nevidă de stări.
• s₀ este starea inițială, element al lui S. Într-un automat finit nedeterminist, s₀ este o mulțime de stări inițiale.
• ${\displaystyle \delta }$ este funcția de tranziție: ${\displaystyle \delta :S\times \Sigma \to S}$. Într-un automat finit nedeterminist, ${\displaystyle \delta :S\times \Sigma \to P(S)}$.
• F este mulțimea stărilor finale, o submulțime a lui S.

Un automat finit transductor (sau translator) este un sextuplu ${\displaystyle <\Sigma ,\Gamma ,S,s_{0},\delta ,\omega >}$, unde:

• ${\displaystyle \Sigma }$ este alfabetul de intrare (o mulțime finită și nevidă de simboluri).
• ${\displaystyle \Gamma }$ este alfabetul de ieșire (o mulțime finită și nevidă de simboluri).
• S este o mulțime finită și nevidă de stări.
• s₀ este starea inițială, element al lui S.
• ${\displaystyle \delta }$ ste funcția de tranziție: ${\displaystyle \delta :S\times \Sigma \to S\times \Gamma }$.
• ${\displaystyle \omega }$ este funcția de ieșire. Dacă funcția de ieșire este o funcție de stare și de alfabetul de intrare ( ${\displaystyle \omega :S\times \Sigma \to \Gamma }$ ), atunci această definiție corespunde modelului Mealy. Dacă funcția de ieșire depinde doar de stare ( ${\displaystyle \omega :S\to \Gamma }$ ), atunci această definiție corespunde modelului Moore.

Optimizarea unui automat finit înseamnă găsirea automatului finit cu numărul minim de stări care operează cu aceeași funcționalitate. Această problemă se poate rezolva folosind un algoritm de colorare.

Într-un circuit digital, un AF poate fi construit folosind un dispozitiv logic programabil, un controller logic programabil, porți logice cu bistabili sau relee. Mai exact, o implementare hardware necesită un registru pentru a stoca variabilele de stare, un bloc de logică combinațională care determină tranziția de stare, și un alt bloc de logică combinațională care determină ieșirea automatului finit.

În general, pentru a construi aplicații software cu automate finite, se folosesc următoarele concepte:

• automat finit condus de evenimente
• automat finit virtual

• Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4
• Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
• Carroll, J., Long, D. , Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall. Englewood Cliffs, 1989.
• Hopcroft, J.E., Ullman, J.D., Introduction to Automata Theory, Languages and Computation. Addison -Wesley, 1979.
• Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
• Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
• Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
• Watson, B.W., Taxonomies and Toolkits of Regular Language Algorithms. Ph.D dissertation, Eindhoven University of Technology, Netherlands, 1995, ISBN 90-386-0396-7.

• Descrierea de pe Free On-Line Dictionary of Computing^{[nefuncțională]}
• Automatele finite în dicționarul NIST pentru algoritmi și structuri de date
• Mașini ierarhice de stare

• Tehnologia informației
• Informatică
• Automate celulare