Automat finit

De la Wikipedia, enciclopedia liberă

Fig.1 Automat finit
Extinde
Fig.1 Automat finit

Un automat finit (AF) sau o maşină cu stări finite 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.

Cuprins

[modifică] Clasificare

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

[modifică] Acceptoare

Fig. 2 AF acceptor care parsează cuvântul "bine"
Extinde
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.

[modifică] 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:

Imagine:Control usa cu AF Moore.png
Fig. 3 Transductor AF: Un exemplu de maşină Moore
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
Extinde
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".

În practică se folosesc deseori modele hibride.

Mai multe detalii despre diferenţele dintre modelele Mealy şi Moore, precum şi despre utilizarea lor, se pot găsi în nota tehnică externă "Moore or Mealy model?".

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.

[modifică] Logica automatelor finite

Fig. 5 Logica automatelor finite
Extinde
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.

[modifică] Modelul matematic

În funcţie de tip, există mai multe definiţii. Un automat finit acceptor este un cvintuplu<Σ, S, s0, δ, F>, unde:

  • Σ este alfabetul de intrare (o mulţime finită şi nevidă de simboluri).
  • S este o mulţime finită şi nevidă de stări.
  • s0 este starea iniţială, element al lui S. Într-un automat finit nedeterminist, s0 este o mulţime de stări iniţiale.
  • δ este funcţia de tranziţie a stării: δ: S x ΣS.
  • F este mulţimea stărilor finale, o submulţime (posibil vidă) a lui S.

Un automat finit transductor este un sextuplu <Σ, Γ, S, s0, δ, ω>, unde:

  • Σ este alfabetul de intrare (o mulţime finită şi nevidă de simboluri).
  • Γ este alfabetul de ieşire (o mulţime finită şi nevidă de simboluri).
  • S este o mulţime finită şi nevidă de stări.
  • s0 este starea iniţială, element al lui S. Într-un automat finit nedeterminist, s0 este o mulţime de stări iniţiale.
  • δ ste funcţia de tranziţie a stării: δ: S x ΣS x Γ.
  • ω este funcţia de ieşire.

Dacă funcţia de ieşire este o funcţie de stare şi de alfabetul de intrare (ω: S x ΣΓ ), atunci această definiţie corespunde modelului Mealy. Dacă funcţia de ieşire depinde doar de stare (ω: SΓ ), atunci această definiţie corespunde modelului Moore.

[modifică] 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.

[modifică] Implementare

[modifică] Aplicaţii hardware

Fig. 6 Diagrama circuitului unui numărător TTL pe 4 biţi, un tip de automat finit
Extinde
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.

[modifică] Aplicaţii software

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

  • automat finit condus de evenimente
  • automat finit virtual

[modifică] Unelte de lucru

  • Bibliotecă pentru AF de la AT&T FSM Library™ [1]
  • AutoFSM [2]
  • Bandera [3]
  • Boost Statechart Library [4]
  • CAZE - FSM-based .NET authorization library [5]
  • Covered [6]
  • Concurrent Hierarchical State Machine [7]
  • DescoGUI [8]
  • Dynamic Attachment Finite State Machine (DAFSM) [9]
  • Exorciser [10]
  • Finite State Kernel Creator [11]
  • Finite State Machine Editor [12]
  • Finite State Machine Explorer [13]
  • 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]
  • Xerox Finite-State Software Tools [40]
  • XTND (XML Transition Network Definition) [41]

[modifică] 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.


[modifică] Alte legături


Notă: Articolul este tradus şi adaptat după Automat finit („Finite automaton“ în engleză)