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.

Starea curentă/ Condiția	Starea A	Starea B	Starea C
Condiția X	...	...	...
Condiția Y	...	Starea C	...
Condiția Z	...	...	...

Î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.

Clasificare

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

Acceptoare

Fig. 2 AF acceptor care parsează cuvântul "bine"

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.

Transductoare

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ă".

Fig. 4 Transductor AF: Un exemplu de automat Mealy

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.

Logica automatelor finite

Fig. 5 Logica automatelor finite

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.

Modelul matematic

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

$\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.
$\delta$ este funcția de tranziție: $\delta :S\times \Sigma \to S$ . Într-un automat finit nedeterminist, $\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 $<\Sigma ,\Gamma ,S,s_{0},\delta ,\omega >$ , unde:

$\Sigma$ este alfabetul de intrare (o mulțime finită și nevidă de simboluri).
$\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.
$\delta$ ste funcția de tranziție: $\delta :S\times \Sigma \to S\times \Gamma$ .
$\omega$ este funcția de ieșire. Dacă funcția de ieșire este o funcție de stare și de alfabetul de intrare ( $\omega :S\times \Sigma \to \Gamma$ ), atunci această definiție corespunde modelului Mealy. Dacă funcția de ieșire depinde doar de stare ( $\omega :S\to \Gamma$ ), atunci această definiție corespunde modelului Moore.

Optimizare

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.

Implementare

Aplicații hardware

Fig. 6 Diagrama circuitului unui numărător TTL pe 4 biţi, un tip de automat finit

Î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.

Aplicații software

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

Unelte de lucru

Bibliotecă pentru AF de la AT&T FSM Library™ [1]
AutoFSM [2]
Bandera [3]
Boost Statechart Library [4] Arhivat în 15 februarie 2006, la Wayback Machine.
CAZE - FSM-based .NET authorization library [5] Arhivat în 9 februarie 2006, la Wayback Machine.
Covered [6]
Concurrent Hierarchical State Machine [7]
DescoGUI [8]
Dynamic Attachment Finite State Machine (DAFSM) [9]
Exorciser [10] Arhivat în 26 aprilie 2006, la Wayback Machine.
Finite State Kernel Creator [11]
Finite State Machine Editor [12]
Finite State Machine Explorer [13]

FIRE Engine, Station and Works [14]
FSMGenerator [15]
Grail+ [16] Arhivat în 4 aprilie 2006, la Wayback Machine.
FSA Utilities [17] Arhivat în 16 februarie 2006, la Wayback Machine.
Libero [18] Arhivat în 5 februarie 2005, la Wayback Machine.
Java Finite Automata [19]^{[nefuncțională]}
JFLAP [20]
jrexx-Lab [21] Arhivat în 17 martie 2006, la Wayback Machine.
JSpasm [22]
Kara [23]
Nunni FSM Generator [24] Arhivat în 26 noiembrie 2005, la Wayback Machine.
Petrify [25]
PyFSA [26] Arhivat în 13 martie 2006, la Wayback Machine.
Qfsm [27]
Quantum-Leaps [28]

Ragel [29]
RWTH FSA Toolkit [30]
SCXML (State Chart XML) [31]
SFST, the Stuttgart Finite State Transducer Tools [32]
Statestep [33]
StateWORKS [34]
State Machine Compiler [35]
Supremica [36]
UniMod [37]
visualSTATE [38]
WhatOS [39] Arhivat în 19 februarie 2006, la Wayback Machine.
Xerox Finite-State Software Tools [40] Arhivat în 12 martie 2006, la Wayback Machine.
XTND (XML Transition Network Definition) [41]

Bibliografie

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.

Alte legături

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