IMPLEMENTAREA UNEI APLICATII DE COMANDA SI CONTROL PENTRU COMANDA UNEI INTERSECTII SEMAFORIZATE

IMPLEMENTAREA UNEI APLICATII DE COMANDA SI CONTROL PENTRU COMANDA UNEI INTERSECTII SEMAFORIZATE

3.1 Introducere in teoria structurala a automatelor finite programabile

Subcapitolul 3.1 isi propune sa introduca conceptul de automat programabil in cadrul acelei clase de sisteme automate care sunt automatele finite, pornind de la ideea necesitatii utilizarii unor astfel de structuri programabile pentru realizarea unor automate secventiale de mare complexitate. Pentru a pastra rigurozitatea in tratarea procedurilor de elaborare a arhitecturii acestor automate, dupa o prima sectiune in care sunt date cateva definitii care permit clasificarea si caracterizarea automatelor fin 333f52d ite si principalele posibilitati de formalizare a evolutiei acestora, se studiaza realizabilitatea automatelor din punct de vedere al echivalarii comportarii intrare-iesire prin automate simple.

3.1.1 Notiunea de automat. Definitii. Clasificari.

Pornind de la esenta conceptuala a sistemului dinamic, prin care i se asociaza un model matematic ce reflecta o tranzitie cauzala in contextul variabilitatii temporale, se poate defini automatul ca un sistem dinamic a carui comportare se poate descrie ca o succesiune de evenimente (stari) ce apar la momente discrete ale variabilei timp. Termenul de automat (finit), adoptat unanim in literatura de specialitate de limba romana trebuie acceptat ca un concept abstract, fara legatura directa cu ceea ce se intelege de obicei prin termenul de "automatizare", dar cu derivatie directa din conceptul de "sistem dinamic (automat) cu reactie negativa", existenta unei reactii inverse interne putand fi pusa in evidenta in structurile complexe de automate finite. Un automat finit, considerat o "cutie neagra", interactioneaza cu mediul prin aceea ca, la un anumit moment , este supus unui semnal de intrare , iar ca raspuns la acesta, ofera la iesire la momentul un semnal de iesire . Faptul ca atat semnalele de intrare, cat si semnalele de iesire, sunt, de regula, succesiuni de valori logice binare sau , si ca aplicarea intrarilor, cat si succesiunea iesirilor, se face in ordine secventiala, justifica denumirea de scheme logice secventiale sub care se mai definesc automatele finite . De altfel, teoria automatelor finite este, in esenta, teoria algebrica a semigrupurilor.

In ceea ce urmeaza, se va incerca o definire riguroasa a conceptului abstract de automat finit si o serie de clasificari ce decurg de la aceasta.

Multimea reprezinta multimea semnalelor de intrare (in numar finit), sau alfabetul finit de intrare (un element se numeste simbol de intrare).

Multimea reprezinta o multime finita a starilor (un element poarta numele de stare).

Multimea reprezinta multimea (finita) a semnalelor de iesire sau alfabetul finit de iesire (un element se numeste simbol de iesire).

Functia poarta denumirea de functie de tranzitie; prin ea se precizeaza starea in care ajunge automatul in urma aplicarii unei intrari (starea viitoare).

Functia poarta denumirea de functie de iesire; prin ea se precizeaza iesirea pe care o ofera automatul in urma aplicarii unei intrari (intrarea viitoare).

In figura 3.1. se prezinta schematic structura de automat corespunzatoare definitiei 1.

Fig. 3.1 Structura unui automat

Informatia este "purtata" in directia indicata de sageti. Circuitele care calculeaza functiile si sunt circuite logice combinationale (CLC), iar elementul de memorie (EM) permite stocarea starii actuale a automatului (starea la timpul prezent).

Automatului i se ataseaza trei semigrupuri libere , , , generate de multimile , , . Elementele semigrupului liber vor fi siruri definite de simboluri din , numite cuvinte de intrare. Similar, elementele semigrupurilor libere si, respectiv vor fi siruri finite de stari, respectiv simboluri de iesire, numite cuvinte de stare, respectiv cuvinte de iesire.

In acest sens, se va face o extindere naturala a domeniilor de definitie pentru functiile de tranzitie si de iesire de la la cu iesire in , respectiv .

Un caz particular de automat finit il constituie automatul de tip Moore, care are functia de iesire . La un astfel de automat, legatura punctata din figura 3.1 dispare.

De remarcat ca, in sens larg, definitia automatului de tip Mealy nu implica finititudinea multimilor , , , dar, in lucrarea de fata, referirile se fac numai la automate finite. In cele ce urmeaza, prin automat se intelege un automat finit.

Daca starea nu este unica, ci exista o multime nevida de stari initiale, automatul se numeste slab initial.

Intr-un astfel de sir, este starea corespunzatoare evenimentului punerii in functiune a automatului.

O categorie interesanta de subautomate este constituita din acelea la care , si , adica cu un numar mai redus de stari.

Macroautomatul atasat automatului este intotdeauna determinist

Conceptul de semiautomat este util pentru studierea separata a tranzitiilor starilor, esentiale in evolutia starilor. Fiecarui automat i se poate asocia un semiautomat unic.

Deoarece de la starea initiala la starea finala automatul trece prin tranzitii succesive prin diferite stari, o problema esentiala este aceea de a preciza posibilitatea atingerii unei stari dintr-o stare .

In acest context, starea este c-succesor al starii , iar este c-predecesor al lui . Daca , atunci este u-succesor imediat al lui , este u-predecesor imediat al lui .

Se demonstreaza usor ca, pentru un automat, oricare ar fi , , , sunt adevarate relatiile:

(3.1)

Evident, automatul este conex de stare daca .