Tabel de tranziție de stat
În teoria automatelor și a circuitelor secvențiale , un tabel de tranziție de stare sau un tabel de stare este un tabel care arată care stare (sau stări, în automatele finite nedeterministe) se va deplasa numărul finit al automatului de stare , pe baza stării sale actuale și pe baza altor intrări . O tabelă de stări este în esență o tabelă de adevăr în care este introdusă și starea curentă și următoarea stare ca ieșire.
Un tabel de stări este unul dintre modurile în care poate fi specificat comportamentul unui număr finit de stări automat . Alte modalități de a face acest lucru sunt: diagrama de stare și ecuația caracteristică .
Forme posibile
Tabel de stare unidimensional
Tabelele de stare de acest tip se mai numesc „tabele caracteristice”, sunt tabele de stare unidimensionale și sunt mult mai asemănătoare cu o tabelă de adevăr decât cu versiunea bidimensională a tabelelor de stare. Intrările sunt de obicei plasate în stânga, separate de ieșirile, care sunt în dreapta. Ieșirile reprezintă următoarea stare a mașinii. Un exemplu simplu de mașină de stare cu două stări și două intrări este după cum urmează:
| LA | B. | Starea curenta | Următoarea stare | Ieșire |
|---|---|---|---|---|
| 0 | 0 | S 1 | S 2 | 1 |
| 0 | 0 | S 2 | S 1 | 0 |
| 0 | 1 | S 1 | S 2 | 0 |
| 0 | 1 | S 2 | S 2 | 1 |
| 1 | 0 | S 1 | S 1 | 1 |
| 1 | 0 | S 2 | S 1 | 1 |
| 1 | 1 | S 1 | S 1 | 1 |
| 1 | 1 | S 2 | S 2 | 0 |
S 1 și S 2 sunt reprezentate în mod obișnuit cu biți simpli (0 și 1), deoarece un singur bit poate avea doar două stări.
Tabel de stare bidimensional
Tabelele de tranziție de stare sunt de obicei tabele bidimensionale. Există două forme comune pentru aceste tabele:
- Una dintre dimensiuni indică starea curentă, în timp ce cealaltă dimensiune indică evenimente. Intersecțiile dintre rânduri și coloane indică următoarea stare a unui eveniment și (opțional) o acțiune asociată cu tranziția de stare.
| Stare \ Eveniment | Și 1 | Și 2 | ... | Și n |
|---|---|---|---|---|
| S 1 | - | S y / A j | ... | - |
| S 2 | - | - | ... | S x / A i |
| ... | ... | ... | ... | ... |
| S m | S z / A k | - | ... | - |
(S: stare, E: eveniment, A: acțiune, -: tranziția nu este permisă)
- Una dintre dimensiuni indică starea (sau stările) curente, în timp ce cealaltă dimensiune indică starea (sau stările) următoare. Intersecția rândurilor și coloanelor indică evenimentul care duce la o anumită stare următoare.
| Stare curentă \ Stare următoare | S 1 | S 2 | ... | S m |
|---|---|---|---|---|
| S 1 | - | - | ... | Și x / A i |
| S 2 | Și y / A j | - | ... | - |
| ... | ... | ... | ... | ... |
| S m | - | Și z / A k | ... | - |
(S: stare, E: eveniment, A: acțiune, -: tranziția nu este permisă)
Alte forme de reprezentare
În mai multe mașini cu număr finit cu tranziții simultane, se poate arăta ce este de fapt o tabelă de tranziție de stare n-dimensională, în care grupuri de rânduri mapează grupuri de stări curente cu stări ulterioare. [1] Acesta este un mod alternativ de a reprezenta o comunicare între mașini de stare separate și interdependente.
La cealaltă extremă, mai multe tabele separate au fost utilizate pentru fiecare tranziție într-o singură mașină de stare: tabelele AND / SA sunt similare tabelelor de decizie incomplete în care decizia este implicit și activarea tranziției asociate. [2]
Exemplu
Un exemplu de tabel de tranziție de stare pentru o mașină M și diagrama de stare corespunzătoare este următorul:
| Diagrama de stare |
Toate intrările posibile la aparat se află în coloanele tabelului. Toate stările posibile sunt în rânduri. Puteți vedea că dacă mașina este în starea S 1 (prima linie), iar următoarea intrare este caracterul 1 , atunci mașina va rămâne în starea S 1 . Dacă intrarea are un caracter 0 , mașina va trece la starea S 2 , așa cum se poate vedea în a doua coloană. În diagramă, același comportament poate fi observat cu săgeata îndreptată de la S 1 spre S 2 , etichetată cu un caracter 0 . Acest proces poate fi descris statistic folosind Lanțurile Markov .
În cazul unui automat de stare finită nedeterminist (NFA), o nouă intrare poate aduce mașina într-un număr de stări mai mare decât una. Acest lucru este indicat în tabel folosind o pereche de paranteze {} cu setul de stări de destinație în interior.
Transformarea tabelului într-o diagramă de stare și invers
Puteți desena o diagramă de stare din tabel. Secvența de pași este următoarea:
- desenează cercurile reprezentând stările
- pentru fiecare stare, citiți toate liniile și desenați o săgeată pentru fiecare stare țintă (sau stări).
- atribuiți numele inițial al stării
- atribuiți numele stării de acceptare unuia sau mai multor state
Notă
- ^ (EN) Michael Breen, Experiența utilizării unei metode de specificație formală ușoară pentru o linie de produse pentru sisteme încorporate comerciale * (PDF), 29 aprilie 2005, DOI : 10.1007 / s00766-004-0209-1 .
- ^ (EN) Specificația cerințelor pentru sistemele de control al proceselor (PDF) pe sunnyday.mit.edu, 9 septembrie 1994.
