LPS - Macchine a stati finiti

 :: LPS - Macchine a stati finiti ::

Che cosa sono

Si tratta di uno strumento formale ed operazionale di modellizzazione. Questi termini hanno un preciso significato: operazionale è contrapposto a dichiarativo, mentre formale è opposto sia a informale che a semiformale. Vediamo un po'.

• informale = una specifica descritta secondo il linguaggio naturale, quindi poco chiaro, confuso
• semiformale = una cosa come UML, possibilmente con l'ausilio di grafici
• formale = una specifica ben precisa che può essere operazionale oppure dichiarativa.

Ecco qual'è la differenza:

• operazionale = descrivo il sistema in base al suo comportamento
• dichiarativo = descrivo il sistema in base alle sue proprietà

Per esempio, una definizione operazionale di un cerchio è "insieme dei punti equidistanti da un centro". La definizione dichiarativa è invece "insieme dei punti tali che XO = c, dove X sono le coordinate del punto e O quelle del centro".

Una FSM può essere rappresentata in modo equivalente da una notazione formale, oppure da un grafo opportunamente disegnato. I nodi equivalgono agli stati del sistema, mentre gli archi sono le transizioni di stato, e le etichette degli archi sono le modalità di transizione.

Di base, le FSM ricevono input. Se producono output, sono dette macchine di Mealy o Moore, di scarabottoliana memoria. Si possono usare per modellare tanta roba, ma hanno anche dei limiti: ad esempio, non sono in grado di modellare requisiti basati sul tempo o sulle performance, e non si possono comporre. Tutto questo sarà più chiaro in seguito.

Definizione matematica

Una FSM è una tripla (S, I , δ), dove:

• S = insieme di stati
• I = insieme degli eventi di input
• δ = funzione di transizione f:S x I -> S. Vuol dire che parte dal prodotto cartesiano di S per I, e porta a S: in altre parole, da uno stato, per via di un certo input, arriva in un altro stato.

Come dicevo sopra, la notazione grafica e quella matematica sono equivalenti. Il grafo è un grafo orientato, perché gli archi hanno una direzione.

Le etichette degli archi, nel grafo, rappresentano gli input.

Per quanto riguarda δ, va notato che queste due scritture sono equivalenti:

 δ(s1, i) = s2 =  δ(s1, i, s2)

Ed ecco un esempio di una FSM in cui l'"orientatezza" del grafo si nota di più:

FSM di Mealy e di Moore

Una macchina di Mealy è una FSM che, per ciascuna transazione, produce un output. Una macchina di Moore invece è una FSM che produce output per ciascuno stato. Vediamo di tuplizzare anche codeste robe:

Macchina di Moore

Macchina di Moore = tupla (S, I, O, δ, λ, F), dove

• S: insieme finito di stati
• I: insieme finito di eventi di input
• O: insieme finito di eventi di output
• δ: S x I -> S : funzione di transizione
• λ: S -> O: funzione di output
• F incluso in S: insieme di stati finali

Macchina di Mealy

Macchina di Mealy = tupla (S, I, O, δ, λ), dove

• S: insieme finito di stati
• I: insieme finito di eventi di input
• O: insieme finito di eventi di output
• δ: S x I -> S : funzione di transizione
• λ: S -> O: funzione di output

Di solito nelle macchine di Mealy si indica anche lo stato iniziale s₀, appartenente ad S.

I diagrammi che rappresentano le macchine di Mealy hanno gli archi etichettati da i/o, dove i è l'evento di input, e o è l'evento di output. Gli eventi di output possono anche essere azioni che la macchina compie.

È inoltre comodo vedere una FSM di Mealy come una tupla (S, I, O, T), dove, oltre alle solite cose, ho T che è l'insieme delle transizioni.
Le transizioni sono, a loro volta, una tupla (s, i, o, s'):

• s = stato sorgente
• i = evento di input
• o = eventi di output
• s' = stato target

D'ora in poi noi useremo FSM di Mealy, e le chiameremo solo FSM, con buona pace di Mealy.

Limiti delle FSM

Si può solo rappresentare un numero finito di stati: i pallogrammi infiniti non sono pratici. Per questo motivo, non è modellabile il tempo continuo come input: essendo continuo, non discreto, ed infinito, dovrei avere uno stato per ogni infinitesimo istante.

L'altro limite è che non sono composizionali. Vuol dire che quando metto insieme due macchine, una con un numero n di stati, e l'altra con m stati, avrò una FSM con n*m stati, e non n+m come potrei supporre.

Questo limite viene a galla quando si cerca di modellare tramite FSM dei sistemi distribuiti o a componenti, in cui ogni componente va per la sua strada, e comunica con gli altri componenti. Dovrei avere uno stato per ogni associazione di stati di un componente con ognuno degli stati dell'altro componente, e così via.

Esempio di composizione di FSM

Ho un Produttore, un Consumatore ed un Magazzino con capienza di 2 unità.

Il Produttore ha due stati: va dall'uno all'altro prima producendo qualcosa, e poi depositandolo nel magazzino.

Il Consumatore ha due stati: va dall'uno all'altro prima prendendo qualcosa dal magazzino, e poi utilizzandolo.

Il Magazzino ha tre stati, se lo immaginiamo con capienza di 2 oggetti. C'è lo stato in cui è vuoto, quello in cui ha 1 oggetto, e quello in cui ne ha 2, e relative transazioni legate al fatto che il Produttore deposita e il Consumatore preleva.

Orbene: se volessi comporre queste FSM, quanti stati ottengo? Forse 2 + 2 + 3 = 7? No: in realtà ne ottengo 12 = 2 * 2 * 3. Infatti, devo avere queste combinazioni

• produttore produce, magazzino vuoto, consumatore consuma
• produttore produce, magazzino vuoto, consumatore preleva
• produttore deposita, magazzino 1, consumatore consuma
• produttore deposita, magazzino 1, consumatore preleva
• produttore produce, magazzino 2, consumatore consuma

etc. etc. Uno stato rappresenta uno stato della macchina: se la macchina ha tanti componenti, allora ho tanti stati, che rappresentano tutte le combinazioni di modi in cui i componenti possono trovarsi tra di loro.

Per oltrepassare questo limite, occorrono altre macchine, che vedremo poi, dette macchine di comunicazione.

Proprietà delle FSM

Adesso segue una bella lista di proprietà relative alle FSM

Equivalenza di stati

Due stati di una FSM sono equivalenti se, per ogni sequenza di input, le sequenze di output provenienti dai due stati sono le stesse.

Vuol dire che devo avere due transizioni così:

• (s1, a, 0, s3)
• (s2, a, 0, s3)

Se 2 stati non sono equivalenti, allora sono distinguibili. Se una macchina non ha coppie di stati equivalenti, è detta minimizzata o ridotta. Ci sono degli algoritmi che individuano le coppie di stati equivalenti e li fanno collassare in un unico stato.

Inoltre, se due macchine hanno gli stati "accoppiabili", sono equivalenti. Per essere precisi, se ho una macchina M1 ed una M2, per essere equivalenti:

• per ogni stato s di M1 deve esistere uno stato s' di M2 tale che s ed s' siano equivalenti
• per ogni stato s di M2 esiste uno stato s' di M1 tale che s' e s sono equivalenti

Se 2 macchine non sono equivalenti, sono distinguibili.

K-equivalenza

2 stati sono k-equivalenti se, per ogni sequenza di input di lunghezza k, le sequenze di output dei 2 stati sono le stesse. Si può anche definire la k-distinguibilità allo stesso modo, ed estendere la definizione alle macchine k-equivalenti.

La sequenza di input la si deve vedere così: parto da uno stato e applico quella sequenza di input. Ogni passo di questa sequenza attiverà una transizione che mi porterà o nello stesso stato, o in altri stati etc e produrrà un certo output. Se la stessa sequenza, fatta a partire da un altro stato, mi produce lo stesso output, allora i due stati sono k-equivalenti, con k che è la lunghezza di tale sequenza di input.

FSM completamente specificata

Una FSM è completamente specificata se, per ogni stato e per ogni input, c'è una transizione che comprende questa accoppiata. Ciò vuol dire che, se ho 3 stati e 4 input, tutti e tre gli stati devono saper gestire i 4 input diversi, per poter definire la macchina come completamente specificata.

In generale, però, le macchine con cui abbiamo a che fare NON sono completamente specificate. La cosa è anche intuitiva: è un po' inutile specificare che cosa succede quando premo l'acceleratore elettronico di un'automobile spenta, per intenderci.

Ci sono anche dei sistemi per ottenere una macchina completamente specificata a partire da una macchina non completamente specificata.

Metodo delle transazioni implicitamente definite

Aggiungo agli stati dei loop, con output null oppure '''error',, in corrispondenza con gli input precedentemente non gestiti.

Ad esempio, se dei 3 input un certo stato ne gestisce solo 2, il terzo lo metto in una transizione di loop e ne etichetto l'output come null oppure '''errore'.

Metodo delle transazioni indefinite per default

Questo è veramente balordo. Ad uno stato a cui manchi la gestione di qualche input, devo aggiungere tante transizioni quanti sono (input)x(output)x(stati)!

Per capire la follia di questo sistema, se ho 3 stati, 4 input e 2 output, e il mio stato (il numero 1) gestisce solo 2 input, devo aggiungere una transazione che porta ad ogni stato (anche transazioni di loop) mancante per ogni input, per ogni output: mi mancano 2 input, ho 3 stati e 2 output => 2 * 3 *2 = 12 transazioni.

Un'assurdità.

Metodo della transazione proibita

Semplicemente, scrivo da qualche parte che "non si può applicare questi input allo stato s_i"...

FSM deterministica

Una FSM è deterministica se, dato uno stato ed un input, il passo che può fare è determinato. Questo significa che, se ho un certo input che arriva in uno stato, il passo successivo è solo 1. Se ne ho 2 diversi, allora non è deterministica, perché non saprei determinare con esattezza quale passo fare. Deve esserci quindi una sola uscita per ogni input.

FSM fortemente connessa

Una FSM è fortemente connessa se, per ogni coppia di stati, c'è una sequenza di input che li congiunge.

La sequenza di input, come dicevamo prima per la k-equivalenza, viene applicata a partire dal primo stato. Questo stato reagirà in modi diversi: dopo tot input saremo finiti in un certo punto.

FSM inizializzata

Una FSM è inizializzata se esiste uno stato s_init segnato come stato iniziale.

ATTENZIONE LA LEZIONE 10 NON E' PIU' OGGETTO D'ESAME QUEST'ANNO

Le FSM che considereremo nei vari esercizi etc., sono da considerarsi:

• minimizzate
• completamente specificate
• deterministiche
• inizializzate

Sequenze particolari

Adesso vediamo alcune sequenze di input che hanno delle proprietà particolari. Queste sequenze hanno un senso in un particolare contesto, che viene indicato per ogni sequenza.

Sequenze di sincronizzazione

Il problema è: non so qual'è lo stato iniziale, e voglio mandare in input una sequenza di input tale che lo stato finale sia noto.

Una sequenza è una synchronizing sequence se, applicata a partire da uno qualunque degli stati, essa conduce sempre allo stesso stato finale. Da notare che non ci interessa l'output, ma solo lo stato finale.

Homing sequences

Anche qui, non so quale sia lo stato iniziale, ma voglio conoscere lo stato finale osservando l'output.

Una sequenza di input è homing se, dopo averla applicata, siamo in grado di determinare lo stato finale osservando la sequenza degli eventi di output. Una sequenza di sincronizzazione è anche homing, ma non il contrario (synchronizing)⊂(homing)

Distinguishing sequence

Non so quale sia lo stato iniziale, ma, osservando l'output, voglio scoprire quale sia. Se sono in grado di farlo, applicando una certa sequenza di input, allora quella sequenza di input è detta distinguishing. Alla fine della sequenza so con certezza in quale stato ero alla partenza.

State verification - Unique Input/Output (UIO) sequence

Non conosco lo stato iniziale, e voglio stabilire se un certo stato è iniziale osservando l'output.

Una sequenza è UIO se, dopo averla applicata in input, posso determinare se lo stato iniziale fosse un particolare s_n oppure no; in caso negativo potrei non sapere in quale stato mi trovi.

Macchine a stati finiti estese

Le macchine che abbiamo visto finora non sono in grado di modellare la memoria interna, perché sanno gestire solo input e output. La memoria non è né input né output. Pertanto, per poterla modellare occorre estendere le FSM con il concetto di variabile.

La definizione matematica di una macchina a stati finiti estesa (EFSM) è la seguente: una tupla (S, I, O, V, T), dove S, I, O sono le solite cose; V è l'insieme della variabili, e T quello delle transizioni.

Le transizioni, a loro volta, sono definite così: (s, i, o, g, a, s') dove:

• s = stato iniziale
• i = input
• o = output
• g = guardia
• a = assegnamento ad una variabile
• s' = stato finale

Le cose nuove sono la guardia e l'assegnamento ad una variabile. L'assegnamento va beh, si capisce: se la variabile si chiama x e voglio assegnarle il valore 3, faccio x:= 3.

Per quanto riguarda la guardia, invece, si tratta di una condizione booleana che fa sì che la operazione sulla variabile sia eseguita o no. Il fatto che sia booleana ci dice che questa condizione o è verificata, o non lo è. Se è verificata, l'operazione a viene eseguita. Altrimenti, non viene eseguita. Inoltre, la guardia g è definita sulla variabile, e non su input o output.

Per fare un esempio, se scrivo una transizione così: (s1, tasto +, scrivi numero, var >= 0, a:=a + 1, s2), vuol dire che vado dallo stato s1 all's2 quando arriva l'input "tasto +", producendo l'output "scrivi numero", e che la variabile a viene incrementata di 1 solo se la variabile var è >= 0.

La guardia può anche non esserci: in questo caso, l'operazione viene eseguita sempre.

Stato globale

Lo stato globale è definito come una tupla (s, σ), in cui:

• s è uno stato
• σ è una valutazione su V

Essendo V l'insieme delle variabili, questa definizione vuol dire semplicemente che lo stato globale è una fotografia dello stato della macchina in un certo istante. In quell'istante, la macchina sarà in un certo stato s, e le sue variabili avranno un certo valore. La situazione in cui le variabili hanno un certo valore la definisco con la σ (sigma).

Ad esempio, se ho 3 variabili a, b e c, e la situazione è:

• stato = s1
• a = 3
• b = 2
• c = 100

allora lo stato globale è (s1, σ = (a = 3, b = 2, c = 100)).

Transizione globale

Dopo lo stato globale, c'è anche la transizione globale, che è una tupla in cui si definisce uno stato globale iniziale, uno finale, e dell'i/o in mezzo.

La def è la seguente: ((s, σ), i, o, (s',σ')), dove

• (s, σ) = stato globale iniziale
• i, o = input e output
• (s', σ') = stato globale finale

Questa tupla è una transizione globale se esiste una transazione, definita come (s, i, o, g, a, s'), in cui

• σ soddisfa la g
• σ'(v) = σ(exp), dove a è definita come v:=exp

Nell'esempio del salvadanaio elettronico (da inserire...), una transizione ((empty, coin=0), inc, red, (not empty, coin = 1)) è una transizione globale, perché la valutazione sulle variabili σ qui specificata, cioè coin = 0, soddisfa la guarda che, nella macchina, porta dallo stato empty allo stato non empty. Idem per la σ'.

Invece, ((non emtpy, coin = 5), inc, red, (non empty, coin = 7)) non è una transizione globale, perché, se anche σ soddisfa la guardia, la σ' non la soddisfa affatto: nella mia macchina se incremento vado da 5 a 6, e non a 7.

Grafo di raggiungibilità

Un grafo di raggiungibilità lo creo stabilendo che i nodi sono stati globali, e gli archi sono transazioni globali.

Quindi, avrò uno stato per ogni combinazione di stato e di memoria, e archi tante quante le combinazioni tra transizioni "normali" e stato di memoria.

In particolare, se la memoria è finita, allora anche la combinazione tra stati e memoria sarà un numero finito; idem per la combinazione tra transizioni e stati di memoria. E allora, in queste condizioni è possibile trasformare una EFSM in una FSM semplice, in cui ho tanti stati quante sono le combinazioni tra stati della EFSM e stati in cui la memoria può trovarsi in EFSM.

Se ho per esempio 3 stati, e una variabile che può assumere 5 valori, posso ipotizzare che avrò 3*5 stati:

• s1, v = 0
• s1, v = 1
• s1, v = 2

...

Se invece la variabile ha un range infinito, allora la FSM avrebbe un numero infinito di stati, e non sarebbe più una macchina a stati finiti...

Macchine di comunicazione

Sopra si parlave delle macchine di comunicazione come del sistema per ovviare la triste proprietà delle FSM standard quando vengono composte. Le macchine di comunicazione aggiungono al modello delle macchine il concetto di canale di comunicazione. Tramite questo canale le varie FSM possono scambiarsi messaggi per agire come un sistema unico.

Definizione matematica

Una CFSM è una coppia (C, P) dove C è un insieme di canali, e P un insieme di processi.

Il processo è una tupla (S, I, O, T):

• S = stati
• I = input
• O = output
• T = transizioni

La transizione a sua volta è una tupla che può assumere una di queste tre forme:

• (s, null, s')
• (s, c?i, s')
• (s, c!o, s')

E adesso vediamo di fare un po' di ordine.

Il processo, come si sarà capito, è l'equivalente della singola FSM. Lo chiamo processo perché il fatto che possa comunicare con altre FSM lo rende in grado di essere eseguito indipendentemente, ma sincronizzandosi in qualche modo con le altre FSM.

Per quanto riguarda le transizioni, invece, la parte in mezzo, (quella che è null, c?i oppure c!o) ha a che fare con la capacità del processo di inviare messaggi sul canale. Il canale è indicato da c, l'azione che esegue sul canale può essere una ? o una !, e ciò che deriva da quest'azione è i oppure o. Ed ecco la spiegazione:

• null = in questa transizione il processo se ne frega dei canali
• c?i = il processo legge dal canale c e memorizza quello che legge nella variabile i
• c!o = il processo scrive sul canale c ciò che è contenuto nella variabile o

Quando si rappresenta una CFSM, occorre scrivere prima lo schema della CFSM intera, con i vari processi ed i canali direzionati tramite cui parlano. I canali hanno il loro nome, e questo è univoco per tutti i processi.
Poi, i singoli processi vanno scritto come le solite FSM.

CFSM Estese

Facendo un po' il mix di tutto, mi invento a questo punto le CFSM estese, in cui aggiungo ai canali la faccenda delle guardie, delle variabili e delle azioni. Le cose quindi si complicano un po'.

I processi sono definiti come tuple (S, I, O, V, T), dove V sono le variabili.

Anche le transizioni si fanno complicate, perché assumono una di queste tre forme:

• (s, g, a, s')
• (s, g, c?i, s')
• (s, g, c!o, s')

Si tratta praticamente di una fusione tra le transizioni delle EFSM e quelle delle CFSM: infatti ho le guardie, le azioni sulle variabili e le azioni sul canale.

Estensione temporale delle CFSM estese

Non siamo ancora soddisfatti, e vogliamo espandere ulteriormente le CFSM estese appena viste, indicando nelle transazioni anche l'intervallo temporale in cui l'azione può avvenire.

Le transazioni assumono quindi la forma (s, g, a|i/o, s'. [t1, t2]) in cui:

• a|i/o è l'azione: o agisco sulle variabili (a), oppure agisco sull'i/o
• [t1, t2] è l'intervallo temporale in cui può avvenire suddetta azione.

Transizioni e stati globali

Possiamo applicare anche qui il concetto di transizione globale. Una coppia ((θ, σ), (θ', σ')) è detta transazione globale se, per ogni processo P

• θ = <s₁, s₂, ..., s_n> con s_1..n stati dei vari processi P
• σ = una valutazione su C (l'insieme dei canali di comunicazione)

In pratica, le θ sono gli stati dei vari processi, mentre σ mi dice come stanno i canali. La σ è triforme (che aggettivo è?), così come sono 3 le operazioni relative ai canali:

• transizioni con azione null
• transizioni con lettura da un canale
• transizioni con scrittura su un canale

Allo stesso modo, lo stato globale è una fotografia del sistema in un certo istante di tempo, ed è composto da una bella combinazione di tutti gli stati, dei canali etc. etc.

Il grafo di raggiungibilità lo si ottiene mettendo gli stati globali come nodi, e le transizioni globali come archi. Come avevamo visto prima, posso arrivare ad ottenere una FSM di base. Ovviamente, dipende anche dalla quantità di memoria dei vari processi: processi con memoria infinita non sono rappresentabili con macchine a stati finiti.

Torna alla pagina di LPS