Tabel de tranziție de stat

În teoria automatelor și în logica secvențială , un tabel de tranziție de stare este un tabel care arată în ce stare (sau stări în cazul unei mașini de stări finite nedeterministe ) a unei mașini de stări să se deplaseze, pe baza stării curente și a altor intrări. Un tabel de stări este în esență un tabel de adevăr, în care unele dintre intrări sunt starea curentă, iar ieșirile includ starea următoare, împreună cu celelalte ieșiri.

Un tabel de stare este unul dintre mijloacele de specificare a automatelor finite , alte mijloace fiind o diagramă de stare și o ecuație caracteristică .

Forme comune

Tabelele de stare unidimensionale

Cunoscute și sub numele de tabele caracteristice , tabelele de stare unidimensionale seamănă mult mai mult cu tabelele adevărului decât cu versiunile bidimensionale. Intrările sunt, în general, plasate în stânga și separate de ieșirile, care sunt în dreapta. Ieșirile reprezintă următoarea stare a mașinii.

Iată un exemplu simplu de mașină de stări cu două stări și două intrări combinaționale:

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 reprezintă cel mai probabil biții 0 și 1 simpli, deoarece un singur bit poate avea doar două stări.

Tabelele de stare bidimensionale

Tabelele de tranziție de stare sunt în general tabele bidimensionale. Există două forme comune pentru a le aranja.

Tabel de tranziție de stat
  Eveniment de
stat 		E 1 E 2   ...   E n
S 1 - A y / S j ... -
S 2 - - ... A x / S i
... ... ... ... ...
S m A z / S k - ... -

(S: Stat, E: Eveniment, A: acțiune, -: trecere ilegală)

Tabel de tranziție de stat

curentul       următor		 S 1 S 2   ...   S m
S 1 - - ... A x / E i
S 2 A y / E j - ... -
... ... ... ... ...
S m - A z / E k ... -

(S: Stare, E: Eveniment, A: acțiune, -: tranziție imposibilă)

Alte forme

Tranzițiile simultane în mai multe mașini cu stări finite pot fi arătate în ceea ce este efectiv un tabel de tranziție de stare n-dimensională în care perechile de rânduri mapează stările curente (seturi de) stări cu stările ulterioare. Este o alternativă la reprezentarea comunicării între mașini cu stări interdependente.

La cealaltă extremă, tabele separate au fost utilizate pentru fiecare dintre tranzițiile într-o singură mașină de stare: tabelele „ȘI / SAU” sunt ca tabele de decizie incomplete în care decizia referitoare la regulile prezente este implicit l activarea tranziției asociate.

Exemplu

Un exemplu de tabel de tranziție de stare pentru o mașină '' '' M '' 'cu diagrama de stare corespunzătoare este dat mai jos.

Tabel de tranziție de stat
  Intrări de
stat 		1 0
S 1 S 1 S 2
S 2 S 2 S 1
  Diagrama de tranziție de stat
DFAexample.svg

Toate intrările posibile ale mașinii sunt listate în coloanele tabelului. Toate stările posibile sunt listate în rânduri. Cu tabelul de tranziție de stare de mai sus, este ușor de văzut că dacă mașina se află în starea S 1 (primul rând), iar următoarea intrare este 1 , mașina va rămâne în starea S 1 . A 0 permite mașinii să înceapă o tranziție la starea S 2 așa cum este indicat în a doua coloană. Aceasta este ceea ce este reprezentat în diagramă de săgeata care merge de la S 1 la S 2 marcată cu un 0 .

În cazul unui automat finit nedeterminist (NFA), o nouă intrare poate pune mașina în mai multe stări, de unde și numele său nedeterminist. Acest lucru este indicat într-un tabel de tranziție de stare printr-o pereche de acolade {} cu setul de stări țintă în interior.

Un exemplu este dat mai jos.

Tabel de tranziție de stat pentru un NFA
  Intrări de
stare 		1 0 ε
S 1 S 1 {S 2 , S 3 } Φ
S 2 S 2 S 1 Φ
S 3 S 2 S 1 S 1

Aici, o mașină nedeterministă în starea S 1 care citește o intrare de 0 , va fi în două stări în același timp, stările S 2 și S 3 . Ultima coloană definește tranziția juridică a stărilor de specificitate, ε. Acest caracter special permite mașinii să meargă într-o stare diferită în timp ce nu primește nicio intrare. În starea S 3 , NFA se poate deplasa la S 1 fără a consuma un caracter de intrare. Cele două cazuri de mai sus fac din automatul descris un automat finit nedeterminist.

Transformări de la și către o diagramă de stare

Este posibil să desenați o diagramă de stare din tabel. O secvență de pași ușor de urmat este prezentată mai jos:

  1. Desenați cercuri pentru a reprezenta stările date.
  2. Pentru fiecare dintre stări, măturați linia corespunzătoare și trageți o săgeată spre starea sau stările de destinație. Pot exista mai multe săgeți pentru un caracter de intrare dacă automatul este nedeterminist.
  3. Desemnați un stat ca stat de plecare. Starea inițială este dată în definiția formală a automatului.
  4. Desemnați una sau mai multe stări ca stări finale. Acest lucru este dat și în definiția formală.

Vezi și tu

Emoție la masă

Bibliografie

  1. Breen, Michael (2005), "Experiența utilizării unei metode de specificație formală ușoară pentru o linie de produse pentru sisteme încorporate comerciale", Requirements Engineering Journal 10 (2), doi: 10.1007 / s00766-004-0209-1
  2. Leveson, Nancy; Heimdahl, Mats Per Erik; Hildreth, Holly; Reese, Jon Damon (1994), "Specificația cerințelor pentru sistemele de control al proceselor", IEEE Transactions on Software Engineering 20 (9), doi: 10.1109 / 32.317428

Pentru a afla mai multe