Sisteme Automate

CURS 1

Capitolul I

INTRODUCERE ÎN AUTOMATE FINITE

Introducere

Utilizarea pe scara larga a calculatoarelor a dus la necesitatea studierii lor globale, ca dispozitive de prelucrare a informatiei reprezentata simbolic, în scopul descoperirii de noi resurse de dezvoltare sau a limitarii acestor masini.

Studiul, pentru a fi general, trebuie sa plece de la caracteristici comune – teoria automatelor realizeaza acest studiu al posibilitatilor si limitarilor dispozitivelor de prelucrare a informatiei, folosind un model abstract al tuturor dispozitivelor, model care imita activitatea si aspectul functional al acestora. Acest model abstract de numeste AUTOMAT.

1.1. Definitie

Un automat este un sistem dinamic a carui comportare se poate descrie ca o succesiune de evenimente numite stari, ce apar la momente discrete ale variabilei timp.

Fiecare sistem care opereaza la momente de timp discrete si a carui intrari/iesiri si structura interna îsi poate atribui numai un numar finit de configuratii distincte, poate fi considerat în mod abstract ca fiind un automat finit.

Automatul finit, ca termen, va fi acceptat ca un concept abstract (obiect logico-matematic realizat sau realizabil), fara legatura directa cu notiunea de automatizare, dar cu derivatie directa din conceptul de sistem dinamic cu reactie negativa. Considerat ca o cutie neagra, automatul poate fi reprezentat ca în figura 1.

x (t) Automat z (t)

s (t)

Fig. 1

Daca multimea starilor interne s(t) este finita, automatul este considerat automat finit. Automatul finit interactioneaza cu mediul deoarece la un anumit moment de timp t este supus unui semnal de intrare x(t), iar ca raspuns la iesire ofera la momentul t+dt semnalul z(t). Datorita faptului ca atât semnalele de intrare cât si cele de iesire sunt de regula succesiuni de valori binare (0 sau 1) si aplicarea intrarilor si succesiunea iesirilor se face în ordine secventiala se justifica denumirea de circuit logic secvential (CLS). Automatele finite sunt o reprezentare abstracta a circuitelor logice secventiale.

Automatul infinit este o masina la care multimea starilor, precum si multimea variabilelor de intrare si de iesire sunt infinite. Nu exista un automat infinit realizabil, dar trebuie luat ca limita spre care tind masinile de calcul moderne. În practica, finitudinea masinilor de calcul se datoreaza fie limitarii în timp a functionarii, fie limitarii în complexitate a structurii sau în lungime a secventei de instructiuni. Pentru a se putea studia un automat infinit se foloseste un compromis. Se studiaza acele masini care au la un moment dat o structura finita, structura pe care o pot extinde nedefinit în timp. O astfel de masina este masina Turing, realizata dintr-un automat finit si o memorie extinsa, formata de exemplu dintr-o banda infinita, reprezentând o multime de celule continând elemente ale multimii variabilelor de intrare si de iesire. (Fig. 2)