Automat finit
De la Wikipedia, enciclopedia liberă
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
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:
- 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".
Î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
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
Î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
|
|
[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
- Descrierea de pe Free On-Line Dictionary of Computing
- Automatele finite în dicţionarul NIST pentru algoritmi şi structuri de date
- Maşini ierarhice de stare
Notă: Articolul este tradus şi adaptat după Automat finit („Finite automaton“ în engleză)