edutecnica

Automi a stati finiti        

Un automa è un sistema dinamico, discreto e a stati finiti caratterizzato da:

Un numero finito di ingressi I.
Un numero finito di uscite U.
Un numero finito di stati Q.
Una funzione di trasferimento A che predice lo stato futuro, noto lo stato attuale.
Una funzione di trasferimento T che fornisce le uscite U, noto lo stato e l'ingresso attuale .
Una funzione di trasferimento M (rete di memoria) in retroazione.

automa di mealy

Lo schema di figura rappresenta l'automa di Mealy, nel quale l'uscita dipende direttamente ed istantaneamente dall'ingresso. Esso è anche detto automa improprio.

 

automa di moore

Lo schema di figura rappresenta l'automa di Moore, nel quale l'uscita non dipende dall'ingresso. Esso è anche detto proprio.

I due modelli sono considerati equivalenti; da un automa di Mealy si può ottenere un automa di Moore e viceversa, l'automa di Mealy risulta essere, in genere, più rapido.

Il funzionamento degli automi viene rappresentato tramite i grafici di Mealy, dove gli stati Q sono rappresentati da nodi e le funzioni di trasferimento (o di transizione) da segmenti o archi orientati.

Un esempio di funzionamento di una macchina sequenziale, può essere un dispositivo riconoscitore della sequenza di caratteri 'OK'.

In questo caso l'uscita U={No;Si} cioè la sequenza è stata riconosciuta oppure no.
Gli ingressi possono essere considerati I={O;K} cioè o la lettera O oppure la lettera K, se ipotizziamo di ragionare con una grammatica costituita solo da due simboli.
Col grafo di Mealy si individuano due stati q0 in cui viene riconosciuta la lettera 'O' e q1 in cui viene riconosciuta la lettera 'K'.

 

All'accensione l'automa si posiziona nello stato q0 , se riceve in ingresso la K si porta allo stato q1 in questa fase l'uscita y dell'automa vale sempre NO (0) in quanto l'intera sequenza non è ancora stata riconosciuta.


Una volta che si trova nello stato q1 l'automa, se riceve una O si riporta allo stato q0 con y sempre uguale a 0, mentre se riceve una K si riporta sempre allo stato q0 ma ponendo y=1, che significa che la sequenza 'OK' è stata riconosciuta.


Per schematizzare con cifre binare poniamo: q0=0 e q1=1 sempre affidandoci alle cifre binarie gli ingressi saranno: O=0 e K=1. L'uscita y=1 solo quando la sequenza viene riconosciuta, altrimenti y=0.

Se pensiamo di realizzare l'automa riconoscitore con dei FF-D possiamo ricostruire la tabella in figura, dove sono rappresentati gli ingressi x (O/K) l'uscita Q del FF e il suo stato successivo, coincidente con l'ingresso D del FF; in corrispondenza lo stato y (uscita che rivela il riconoscimento della sequenza quando vale 1).

Lo schema completo dell'automa, sarà dunque il seguente: