Torna alla pagina di Ingegneria del Software
:: Ingegneria del Software - Appunti del 17 Marzo 2009 ::
Automi
Dopo aver visto nella lezione precedente che cosa sono gli automi, partiamo dicendo che gli automi vanno bene, a differenza dei CdU, per indicare la temporizzazione degli eventi, cioè dire quando una cosa accade nel corso del tempo.
Possiamo indicare gli automi anche con la sigla MSF, o FSM all'inglese, che significa macchina a stati finiti. Un automa è infatti una macchina che, una volta fatta "partire", va avanti da sola a seconda di quello che le viene passato in input. Il concetto di "stati finiti" ha a che fare con la rappresentabilità algoritmica dell'automa stesso: un numero infinito di stati non è rappresentabile da nessuno, né con un disegno, né da un computer.
Stimoli e risposte
Nella sua forma più basilare, un automa reagisce con un output a certi input. La funzione di transizione ha quindi la forma f: I -> O.
Per dare qualche definizione, diciamo che
- una parola sull'alfabeto di input è una sequenza di simboli tratti da quelli che la macchina riconosce come input
- una parola sull'alfabeto di output è una sequenza di simboli tratti da quelli che la macchina produce come output
La funzione di transizione definita qualche riga sopra ci dice una cosa importante: l'output dipende solo dall'input, e da nient'altro. Questo significa che la macchina non ha nessuna nozione di quello che è successo prima, perché non ha nessun modo per tenerne traccia: è come picchiare col martelletto sul ginocchio, questo salta, poi torna in attesa, se picchio ancora esso salta ancora e così via.
In altre parole, il modello di FSM così definita è senza memoria, ovvero stateless. Si capisce subito che una FSM fatta in questo modo è limitante, perché non può modellare tantissimi problemi che invece richiedono una risposta diversa allo stesso stimolo a seconda dello stato in cui si trova in quel momento la macchina stessa.
Quindi, se voglio che la macchina risponda ad un certo input anche in funzione dello stato in cui si trova, devo avere un'altra categoria di funzioni che tenga conto anche di questo:
f(I,S) -> O
g(I,S) -> S
ovvero:
- la funzione f(I,S) -> O produce un output a seconda dell'input ricevuto e dello stato attuale
- la funzione g(I,S) -> S mette la macchina in uno stato a seconda dell'input ricevuto e dello stato attuale
Una macchina in qui ho definite entrambe queste funzioni è detta stateful.
Esiste un teorema matematico tramite il quale si può dimostrare che una macchina con output è rappresentabile in modo perfettamente equivalente con una macchina senza output.
Intuitivamente, ciò lo si può ottenere immaginando di "incapsulare" l'output negli stati, ovvero mettere nella descrizione degli stati anche l'output che la macchina dovrebbe produrre sotto quelle condizioni. Certo, il numero di stati in questo modo esploderebbe, ma preserverei l'equivalenza.
A noi non interessa tanto l'equivalenza in sé tra macchine con output e macchine senza output. La cosa veramente interessante è che questa proprietà è dimostrabile matematicamente. Infatti, gli automi sono un linguaggio dotato di semantica, e quindi hanno regole matematiche ben precise e non ambigue che mappano il dominio in un codominio. Il poter maneggiare gli automi in modo matematico ci permette proprio di poter inferire delle proprietà che essi hanno tramite il calcolo, e quindi in modo certo e indiscutibile.
Questa è la grande differenza tra i linguaggi dotati di semantica e quelli che ne sono sprovvisti. Senza semantica non sono in grado di applicare ragionamenti matematici relativi al linguaggio, mentre al contrario la semantica mi permette di adoperare la matematica a questo fine.
Il problema della memoria
Uno stato rappresenta uno stato di esistenza dell'automa in un dato istante. Le funzioni di transizione che mappano una combinazione SxI in uno stato finale S ci permettono di modellare il passaggio da uno stato all'altro della nostra macchina.
Come abbiamo detto sopra, ciò ci permette di rappresentare la memoria della nostra macchina: se mi trovo in un certo stato, è perché ho avuto una certa storia alle mie spalle, e pertanto so reagire di conseguenza.
Si tratta sicuramente di un bel vantaggio rispetto agli automi FSM più semplici, ma c'è un problema essenziale che salta subito all'occhio, ed è dovuto al fatto che la memoria della macchina viene rappresentata dagli stati.
Supponiamo di avere un magazzino che può contenere fino a dieci oggetti. Posso modellarlo con un automa con una combinazione di 11 stati, ciascuno rappresentante la condizione del magazzino in un dato istante: vuoto, 1 oggetto, 2 oggetti... 10 oggetti.
Se voglio raddoppiare il numero degli oggetti, devo raddoppiare il numero degli stati. Ma se, come nel caso della memoria del computer, il limite al numero degli oggetti è altissimo, dovrei allora avere un numero altissimo di stati, e ciò è poco praticabile.
Facciamo ancora un esempio. Il nostro magazzino ha capacità massima di 10 pezzi. Però, se nel caso sopra avevo tacitamente supposto che potevo inserire ed estrarre un solo pezzo alla volta, ora voglio poter inserire o togliere 1, 2 o 3 pezzi alla volta.
Immaginiamo di essere nello stato che rappresenta il magazzino con 5 oggetti dentro. Devono esserci:
- una freccia che porta allo stato 6, quando inserisco un oggetto
- una freccia che porta allo stato 7, quando inserisco due oggetti
- una freccia che porta allo stato 8, quando inserisco tre oggetti
- una freccia che porta allo stato 4, quando tolgo un oggetto
etc. etc.
In caso di memoria molto ampia e di capacità ampie di gestione della stessa, il numero di transizioni esplode in modo incontrollabile.
D'altronde, già il nome stesso della macchina (macchina a stati finiti) mi dice che non posso avere a che fare con un numero infinito di stati.
La soluzione esiste, e consiste nel costruire, separato dal mio automa, un qualche strumento che mi permetta di gestire la memoria. Quanto questa soluzione sia comoda, non si sa.
Il problema della sincronizzazione
Come già visto qui, c'è un grosso problema relativo alla sincronizzazione di due automi separati.
Nel caso in cui io voglia far collaborare due sistemi diversi, ogni macchina deve avere nozione di quello che le altre macchine hanno fatto per poter prendere delle decisioni.
La matematica ci può venire in aiuto, tramite l'operazione di fusione tra due automi diversi. Si tratta di una combinazione condizionata tra tutti gli stati e gli input di un automa, con tutti gli stati e gli input dell'altro automa. Purtroppo, già sappiamo che il prezzo di questa operazione, pure ottenibile in modo automatico, è l'esplosione del numero degli stati.
La soluzione a questo problema c'è, ma consiste nell'abbandonare gli automi per dedicarci alle reti di Petri, che vedremo nella prossima lezione. Possiamo però anticipare alcune cose:
- le reti di Petri sono molto più espressive, ma proprio per questo più ardue da gestire matematicamente
- in questa pagina, alla voce Comunicazione tra macchine, ci sono alcuni indizi sul funzionamento delle reti di Petri nella parte relativa alla sincronizzazione tra macchine differenti, e potrebbe essere utile darci un'occhiata.
Il lemma di espansione
Questo argomento è stato trattato in una lezione successiva, ma riguarda gli automi, e permette di comprenderne meglio alcune caratteristiche.
Il lemma di espansione mi dice (in modo informale) che, se ho dimostrato per enumerazione che per arrivare ad un certo stato mi occorre una stringa di una certa lunghezza, allora questa proprietà sarà vera sempre, perché tutte le altre stringhe saranno più lunghe.
Qui ci andrebbe un disegnino...
La cosa interessante è che ho dimostrato che occorre almeno una a per andare fino allo stato KO, e l'ho dimostrato per enumerazione, cioè contando a mano i possibili percorsi. Non ce ne sono altri, e quindi sono felice.
In quest'altro automa (disegnino) invece c'è un ciclo. L'enumerazione totale è impossibile, perché i cicli sono potenzialmente infiniti. Ma se lo dimostro per una stringa per enumerazione, e so che tutte le altre stringhe sono per forza di cose più lunghe, allora per il lemma di espansione posso inferire che si tratti di una proprietà dell'automa.
Torna alla pagina di Ingegneria del Software
