FACULTATEA DE INGINERIE

MASTERAT SACPI

Diagnoza evenimentelor discrete

-Automat finit cu semafoare-

Masterand:

Pál István

Automat finit cu semafoare

- 2011 -Introducere

- Consideratii teoretice -

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 intrareo executată la intrarea într-o stare

Acţiune de ieşireo executată la ieşirea dintr-o stare

Acţiune de intrare de dateo acţiune executată în funcţie de starea prezentă şi de datele de intrare

Acţiune de tranziţieo acţiune executată în momentul unei tranziţii

Automatul Finit poate fi reprezentat printr-o diagramă de stări (sau diagramă de stări şi tranziţii) ca în figura de mai jos:

2

Automat finit cu semafoare

Ca si o clasificare putem distinge două grupuri de automate finite:

Acceptoare

Transductoare

Maşina Acceptoare,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 de mai jos arată un automat finit care acceptă

cuvântul "bine". În acest AF, singura stare finală este starea Succes.

3

Automat finit cu semafoare

Masinile Transductoare, 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.

La masinile Transductoare se disting două tipuri:

Maşina Moore

Maşina Mealy

Automatul Moore, foloseşte doar acţiuni de intrare, şi deci ieşirea depinde doar de stare.

Avantajul modelului Moore este simplificarea comportamentului. Exemplul din figura de

mai jos 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 (1) î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ă".

4

Automat finit cu semafoare

Maşina Mealy 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".

In practică se folosesc deseori modele hibride.

5

Automat finit cu semafoare

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.

Optimizarea unui automat finit înseamnă găsirea automatului finit cu numărul

minim de stări care operează cu aceeaşi funcţionalitate.

Aplicaţii FSM (AF)

Ca aplicaţii hardware 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.

6

Automat finit cu semafoare

Ca exemplu hardware, am atasat imaginea de mai jos, cu diagrama circuitului unui

numărător TTL pe 4 biţi, ca un tip de automat finit.

Aplicaţiile software pentru Automate Finite sunt multiple şi de diversitate foarte

largă. În general, pentru a construi aplicaţii software cu automate finite, se folosesc

următoarele concepte:

automat finit condus de evenimente

automat finit virtual

automate pe bază de programare

O aplicaţie software creată pentru a realiza şi simula automate finite, este aplicaţia

Hades JavaFSM, implementată de Universitatea de Informatică din Hamburg.

7

Automat finit cu semafoare

Această aplicaţie oferă un design simplu, portabil şi un mediu de simulare, care

permite simulări cu circuite digitale şi echipamente active, interfaţa fiind realizată in

mediul Java 6.

Modul interactiv de simulare,permite modificări online, în care intrările de circuit

pot fi modificate prin intermediul mouse-ului sau tastaturii, în timp real. Acest lucru

permite să se stabilească valori de intrare în timp ce se execută o simulare, fără a fi

nevoie să scriem un fişier stimul extern, şi fără o procedură lungă de edit-compilare-

simulare. De asemenea, Hades asigură o interfaţă grafică cu o animaţie mai deyvoltată

decât cele mai multe alte aplicaţii de design electronice.

Pe de altă parte, Hades sprijină pe deplin modele ierarhice, şi toate funcţiile pot fi

încărcate prin scripturi, astfel încât utilizatorii experimentaţi pot crea şi simula sisteme

complexe fără a fi nevoie de un software de proiectare.

Spre deosebire de alte sisteme, în cazul cărora unele modelele de simulare trebuie scrise

în limbaje de programare interne specializate, toate modelele de simulare Hades sunt

scrise direct în Java.

Aceasta oferă utilizatorului un limbaj modern de programare orientat pe obiect cu

o bibliotecă bogată, inclusiv accesul complet la reţea şi o grafică portabilă.

Sistem automat pentru controlul unei parcari, cu semafoare

Sistemul conceput, constă dintr-un spaţiu de acces, spre o parcare cu o capacitate

de 250 locuri, prevăzută cu o barieră şi câte un semafor, atât la intrarea în parcare, cât şi

la ieşire.

Pe străzile de acces sunt prevăzute afişoare care indică dacă sunt locuri libere în parcare.

În cazul în care sunt locuri libere iar semaforul indică culoarea verde (acest lucru arată

faptul că nu este loc în parcare), maşina poate înainta. Când automobilul ajunge înaintea

8

Automat finit cu semafoare

semaforului şi bariera este coborâtă, înseamnă că nu mai sunt locuri în parcare, implicit

culoarea semaforului va fi roşu. După ce a ieşit o maşină, se ridică bariera, semaforul

devine verde, şoferul poate înainta iar în momentul în care acesta ajunge în parcare,

bariera începe să coboare.

Implementarea cu aplicaţia Hades Java Webstart

După accesarea fişierului “hades-webstart.jnlp”, se deschide imaginea cu spatiul

de lucru şi cu meniul principal. Din meniul “Edit” se accesează submeniul “Open

component browser” şi se alege modulul dorit (în cazul nostru un bloc de FSM):

9

Automat finit cu semafoare

În continuare se aleg celelalte module necesare implementării şi se plasează

fiecare, astfel încât conexiunile să fie cât mai vizibile şi corecte.

Este foarte important conectarea intrarilor, respectiv un generator de impuls la intrarea

Reset, un generator de tact la intrarea de Clk, iar o intrare I/O pentru intrarea Stop a

blocului FSM.

Conexiunile se realizează din meniul Edit, cu submeniul Autoconnect object...

10

Automat finit cu semafoare

Iar setările staţiilor şi tranziţiilor precum şi valorile de intrare se setează din meniul edit

de pe blocul FSM:

La conectarea ieşirilor, care se ralizează la fel ca şi intrările, este important să setăm şi

valoarea de ieşire, precum şi (în cazul nostru culoarea LED ului), care indică culoarea

semaforului:

11

Automat finit cu semafoare

Dacă schema de conectare este corectă, se poate testa blocul FSM.

Testarea Blocului FSM in sine, împreună cu valorile de intrare şi valorile de tranziţie se

poate efectua accesând test FSM din Meniul din stânga a editorului FSM.

Schema finală cu toate componentele incluse, funcţionale arată astfel:

12

Automat finit cu semafoare

Maşina funcţionează automat, cu o temporizare prestabilită ( setată iniţial la 1 s),

dar acesta se poate modifica din program.

În momentul în care senzorul Stop este activat semaforul respectiv se stabiliyează la

culoarea verde, permiţând accesul autovehicolului in parcare.

Pentru a asigura timpul de oprire/pornire a maşinii, am introdus culoarea galbenă, astfel

încât între două momente de roşu – verde, există o tranziţie roşu – galben in momentele 2

şi 8.

Proiectul se poate dezvolta, astfel încât bariera să aibă rol mai important în sistem

(momentan doar rol de siguranţă şi funcţionare în cazul defectării sistemului), de

exemplu, realizarea unui sistem automat de tarifare (bazat pe card cu microcip), în acest

caz timpul de balansare roşu - verde, trebuie prelungit din program.

13

Automat finit cu semafoare

Bibliografie

1. Norman Hendrich: HADES Tutorial

2. Meera Sampath, Raja Sengupta: Failure diagnosis using Discrete-Event

Models

3. http://www.fsmlabs.com

4. http://tams-www.informatik.uni-hamburg.de

5. http://www.splatco.com/fsm_tute

6. http://qfsm.sourceforge.net

14