Questa pagina è in costruzione: vi preghiamo di scusare le inesattezze e la grafica trascurataLa teoria degli automi, elaborata fin dagli inizi del secolo scorso (XX), ha dato grande impulso allo sviluppo di quella che poi è stata chiamata la Computer Science . Infatti prima che la tecnologia fosse all'altezza di realizzare i primi prototipi di quelli che oggi chiamiamo computer, la teoria degli automi ne aveva schematizzato il comportamento, secondo modelli che ne rendono possibile lo studio e la progettazione.
Un automa è un particolare tipo di sistema: ovviamente si tratta di un sistema artificiale, cioè realizzato dall'uomo; è anche un sistema aperto, perchè la sua principale caratteristica è quella di ricevere informazioni (segnali) in ingresso, e restituire informazioni (responsi) in uscita.
E' caratterizzato dal fatto di poter assumere un certo numero (non necessariamente finito) di stati interni, che possono influenzare i valori dei segnali in uscita, ed è un sistema invariante , nel senso che le funzioni che ne regolano il comportamente rimangono costanti nel tempo, e dinamico , perchè si evolve nel tempo cambiando i valori assunti dalle variabili (di stato, ingresso e uscita).
In pratica gli automi sono modelli matematici di macchine che desideriamo assumano un certo comportamento; concettualmente sarebbe possibile anche studiare automi continui,nel senso che le variabili di stato, essendo grandezze fisiche, variano in maniera continua: però per semplicità non si considerano i valori di transizione degli elementi, ma solo gli stati stabili, per cui gli automi che studieremo sono sistemi discreti .
Per chiarire questo concetto: in un computer le grandezze 0 e 1 possono essere rappresentate da due differenti valori di tensione (0 e 5 volt) in un condensatore; naturalmente quando passiamo da un valore all'altro, la tensione varierà in maniera continua, ma noi prendiamo in considerazione solo gli stati finali, di 0 e di 5 volt.
In ogni istante di tempo l' automa è caratterizzato dallo stato in cui viene a trovarsi: possiamo definire lo stato come n-pla dei valori assunti dalle n componenti che lo compongono. Se la componente i-sima può assumere ki valori diversi, si avrà che il numero degli stati possibili è:
p = k1 * k2 * ... * kn
Nel caso in cui tutti i valori ki sono finiti, abbiamo un automa a stati finiti, altrimenti abbiamo un automa infinito (ovviamente più diffcile da studiare).
Le macchine a stati finiti o automi finiti si possono definire come un insieme di organi (dispositivi di vario tipo) i quali assumono, nei vari istanti del loro funzionamento, uno fra i possibil stati (che sono in numero finito). Anche gli intervalli di tempo che prendiamo in considerazione sono discreti, cioè il tempo sarà misurato da un qualche tipo di oscillatore (clock al quarzo).
I vari stati possono essere assunti aleatoriamente (a caso) oppure in maniera deterministica: nel primo caso si parla di macchine probabilistiche, nel secondo di automi deterministici
N.B.: il termina macchina è usato in questo contesto come sinonimo di automa
Naturalmente siamo interessati allo studio del secondo tipo di automa
Un automa M è, caratterizzato dai seguenti elementi:
| S = {Si} | un insieme finito di simboli di ingresso o stimoli |
| R = {Ri} | un insieme finito di simboli di uscita o responsi |
| Q = {Qi} | un insieme finito di stati interni |
| F | una funzione di stato o meglio funzione di transizione di stato |
| G | una funzione di uscita |
A seconda di come viene definita la funzione di stato, è possibile distinguere vari tipi di automi. La funzione di stato può dipendere dalle variabili St, cioè dall' insieme degli stimoli in un dato istante t, e da Qt-1, cioè dallo stato nell'istante precedente.
Nel caso che la funzione di stato dipenda da entrambi:
F: S x Q --> Q
abbiamo un automa sequenziale, cioè dotato di "memoria" , in grado di "ricordare" lo stato precedente e comportarsi di conseguenza.
Lo stato del sistema in un istante t dipende quindi dagli stimoli ricevuti nell' istante t-1 e anche dallo stato in cui si trovava in detto istante:
Qt = F (St-1, Qt-1)
Se la F invece è funzione soltanto dello stimolo, cioè
F: S --> Q
abbiamo un automa combinatorio, privo di memoria. Infatti il comportamento della macchina non è influenzato dagli stati assunti in precedenza, lo stato interno assume determinati valori solo in dipendenza dello stimolo applicato, e nell'istante successivo alla mancanza di stimoli assume valori aleatori (casuali) e non prevedibili.
In questo caso si può scrivere:
Qt = F (St-1)
Ora ci occuperemo dello studio degli automi sequenziali. Vengono così detti perchè gli stati sono ognuno in funzione dello stato precedente, e quindi l'ultimo è in un certo senso funzione della sequenza degli stati precedenti.
Esistono due modelli diversi di questi automi, a seconda che il responso sia o no funzione dello stimolo
Il primo modello matematico è detto automa di Mealy, ed è rappresentato con una quintupla del tipo M(S, R, Q, F, G) in cui la funzione G, cioè la funzione di uscita, ha dua variabili indipendenti, lo stato e l'ingresso:
G. S x Q --> R
cioè si può scrivere:
rt=G(St-1, Qt-1)
In questi automi, detti anche automi impropri, la sequenza di uscita è dipende quindi sia dalla sequenza degli stimoli che da quella degli stati.
Il secondo modello, detto automa di Moore, è rappresentato invece da una quintupla M(S, R, Q, F, G) in cui la funzione di uscita G dipende unicamente dallo stato:
G: Q --> R
Possiamo quindi scrivere:
rt=G(Qt-1)
Questi automi sono detti anche automi propri.
A questo punto, definita una sequenza di ingressi e noto lo stato iniziale di una macchina M, conoscendo le funzioni F e G, è nota anche la sequenza degli stati interni e quella dei responsi.
Se la sequenza è lunga h, avremo una sequenza di stati lunga h+1 e una sequenza di responsi lunga h, per l'automa di Mealy, mentre la sequenza di stati e di responsi saranno entrambe lunghe h+1 nel caso di un automa di Moore.
Esistono diverse teniche per rappresentare e studiare il comportamento degli automi:
La rappresentazione a scatola nera non si occupa degli stati interni del sistema ma soltanto degli ingressi e delle uscite.
Questo metodo consiste nel definire gli insiemi degli stimoli, dei responsi e degli stati, e nel descrivere la funzione di transizione di stato e quella degli ingressi.
Prendiamo l'esempio di un semplice automa in grado di ricordare un bit:
Gli ingressi saranno uno 0 o un 1 a seconda di quello che voglio salvare nella memoria:
S={0, 1}
I responsi saranno 0 o 1 a seconda di quello che l'automa contiene:
R = {0, 1}
Gli stat iinterni saranno due: uno per memorizzare lo 0, chiamiamolo q0, e l'altro per memorizzare l' 1, che chiameremo q1
Q= {q0, q1}
La funzione di transizione di stato è, la seguente:
F(0, q0) = q0
F(0, q1) = q0
F(1, q0) = q 1
F(1, q1) = q 1
E la funzione di uscita è data da:
G(0, q0)=0
G(1, q0)=0
G(0, q1)=1
G(1, q1)=1
Notiamo che la funzione di stato non dipende dallo stato precedente ma solo dall' ingresso, e quella di uscita non dipende dall' ingresso ma solo dallo stato. Si potrebbe quindi scrivere:
F(0)=q0
F(1)= q1
G(q0)=0
G(q1)=1
N.B.: questo automa, che rappresenta una memoria, ha la particolarità di essere un automa combinatorio, cioè privo di memoria! Questo perchè non ricorda gli stati precendenti, ma solo l'ultimo ingresso. In realtà si tratta semplicemente di un ritardo, e la funzione delle uscite rispetto agli ingressi è rt = st-1
Per ottenere una memoria stabile, è quindi necessario alimentarlo continuamente con gli ingressi (si può farlo creando opportunamente una retroazione del segnale in uscita).
Questo è un problema che si verifica effettivamente nelle memorie RAM, che hanno bisogno di un refresh periodico per non perdere l'informazione.
| F | 0 | 1 |
| q0 | q0 | q1 |
| q1 | q0 | q1 |
Con questo sistema si rappresentano in una matrice tuttii possibili stati nella prima colonna, e i prossimi stati nella prima riga; all' incrocio tra le due si riportano gli ingressi che causano il cambiamento di stato e le relative uscite.
L'automa degli esempi precedenti viene cosi' descritto:
| t \ t+1 | q0 | q1 |
| q0 | 0 / 0 | 1 / 0 |
| q1 | 0 / 1 | 1 / 1 |
Questo metodo dà una rappresentazione grafica dell'automa M, usando un grafo orientato, in cui gli stati sono simboleggiati da cerchi e i passaggi di stato da frecce, accanto alle quali vengono indicati gli stimoli e i responsi.
Questa pagina è in costruzione: vi preghiamo di scusare le inesattezze e la grafica trascurata
 |
|