Elemente de teorie generala a automatelor
Conceptul de automat ocupa un loc central din punct de vedere teoretic in cadrul unei clase mai largi de sisteme automate, deoarece acestea sunt componente de baza in realizarea fizica a unor structuri programabile secventiale de mare complexitate.
Intuitiv, un automat poate fi considerat ca o cutie neagra prevazuta cu o borna de intrare si una de iesire si este capabila sa posede un anumit numar de stari interne. Automatul interactioneaza cu mediul prin aceea ca la un anumit moment de timp t este supus unui semnal de intrare x(t) si ca raspuns la semnanul de intrare acesta ofera o iesire la momentul t + Delta t un semnal de iesire y(t) si trece intr-o noua stare interna care depinde si de starea automanului la momentul t. Faptul ca atat semnalele de intrare cat si semnalele de iesire sunt de regula succesiuni de valori logice 0 si 1, succesiunea acestora efectuandu-se secvential, justifica faptul ca modul de functionare al automatului este discret. Schimbarea semnalelor de iesire si a starilor interne, precum si aparitia semnalelor de iesire se realizeaza la intervale determinate de timp, numite tacte. Daca starea automatului in tactul urmator si iesirea automatului sunt unic determinate, spunem ca automatul este determinist, in caz contrar automatul este nedeterminist. De exemplu, un algoritm de calcul inseamna o succesiune de etape impreuna cu un set de date initiale. Mai precis, un algoritm este o procedura efectiva ce defineste un sir de stari (rezultate intermediare) si care are ca stare initiala setul de date de intrare si ca stare finala rezultatul urmarit; procedura este determinista; fiecare schimbare de stare fiind determinata fara ambiguitate si conduce la un rezultat dupa un numar finit de momente de timp. Un automat primeste o colectie de date (numite in mod sugestiv intrari) pe care le prelucreaza si apoi emite o alta colectie de date (numite iesiri). Notam cu X multimea intrarilor si cu Y multimea iesirilor. In cursul prelucrarii, la fiecare moment t automatul se afla intr-o anumita stare interna. Notam cu S multimea starilor interne ale automatului. Un element s apartine lui S poarta numele de stare. Multimea X, respectiv Y (multimi finite) se mai numeste alfabetul de intrare, alfabetul de iesire al automatului A. Un element x apartine lui X, y apartine lui Y se numeste simbol sau semnal de intrare/iesire.
Evolutia automatului A poate fi descrisa astfel:
- oricarei perechi (s,x) apartine lui SxX ii corespunde un element f(s,x) apartine lui S care reprezinta starea in care trecere automatul A la momentul t + Delta t, daca el primeste la momentul t intrarea x si se afla in starea s.
- oricarei perechi (s,x) apartine lui S x X ii corespunde un element g(s,x) apartine lui Y care reprezinta iesirea emisa de automatul A la momentul t daca el primeste la momentul t intrarea x si se afla in starea s.
Asadar, evolutia automatului A este descrisa de functiile f : S x X –>S, (s,x) –> f(s,x) si g:SxX—>Y , (s,x) ->g(s,x). Functia f:SxX->S poarta numele de functie de tranzitie(a starilor). Ea precizeaza starea in care trece automatul A ca urmare a aplicarii unei intrari. Functia g:SxX->Y poarta numele de functie de iesire. Ea precizeaza iesirea pe care o produce automatul A ca urmare a aplicarii unei intrari. Astfel, un automat A este un sistem de automat corespunzatoare sistemului ordonat A = (X,S,Y,f,g) unde X,Y,S sunt multimi nevide, iar f si g sunt functii.