Archivio di una finanziaria : SOLUZIONE
 
Occorre innanzitutto proporre un automa improprio (Mealy) che risolva il problema. Successivamente, bisogna accertarsi della sua minimalità, verificando che esso sia in forma ridotta e che ogni suo stato risulti raggiungibile dallo stato in cui ci si trova prima di procedere all'interrogazione. Qualora l'automa proposto non sia minimo, si deve utilizzare l'algoritmo di Paull-Unger per la determinazione delle classi di indistinguibilità. Si ottiene così un automa equivalente in forma ridotta, dal quale vanno poi eliminati gli stati non raggiungibili dallo stato in cui ci si trova prima di procedere all'interrogazione.

INGRESSI
Gli ingressi dell'automa sono sette:

 
1=  lettura del carattere "1"
2 = lettura del carattere "2"
3 = lettura del carattere "3"
4 = lettura del carattere "4" 
5 = lettura di un qualsiasi carattere diverso da "1","2","3" o "4"
6 = inizio dell'interrogazione
7 = interruzione (fine) dell'interrogazione
USCITE 
Le uscite dell'automa sono due:
 
1 = esame della registrazione in corso, oppure registrazione non di interesse, oppure registrazione contenente dati errati, oppure nessuna registrazione
2 = registrazione di interesse
 
STATI:
È necessario poter distinguere le seguenti situazioni: 
 
  • sistema spento (è un particolare stato); 
  • nessuna registrazione in esame (è un altro particolare stato);
  • ritrovamento del primo carattere di una registrazione (sono più stati, poichè esistono più possibilità);
  • ritrovamento del secondo carattere di una registrazione (sono più stati, poichè esistono più possibilità).


Ciò è consentito, ad esempio, da un automa A che possegga i seguenti dieci stati:
 

1 sistema spento
2 nessuna registrazione
3 primo carattere: "1"
4 primo carattere: "2", oppure "3"
5 primo carattere: "4"
6 primi due caratteri: "11"
7 primi due caratteri: "12"
8 primi due caratteri: "41"
9 primi due caratteri: "42"
10 primi due caratteri: "22" o "32"

TABELLE DI TRANSIZIONE E DI USCITA
Ogni automa di Mealy
 

x(t+1) = f(x(t),u(t))
y(t) = h(x(t))

è rappresentato da una coppia di funzioni f e h, assegnabili, ad esempio, attraverso due tabelle dotate di n righe ed m colonne, dove m = numero degli ingressi, n = numero degli stati. 
Nel caso di f, la casella (i,j) contiene lo stato futuro mentre, nel caso di g, indica l'uscita.

È quindi necessario procedere alla compilazione delle seguenti tabelle, nelle quali alcune righe sono state riempite a titolo di esempio.
 

 
1
2
3
4
5
6
7
1
1
1
1
1
1
2
1
2
3
4
4
5
2
2
1
3
             
4
             
5
             
6
2
2
2
2
2
2
1
7
             
8
             
9
             
10
2
2
2
2
2
2
1
Tab.1: tabella di transizione
 
1
2
3
4
5
6
7
1
1
1
1
1
1
1
1
2
1
1
1
1
1
1
1
3
             
4
             
5
             
6
2
1
1
1
1
1
1
7
             
8
             
9
             
10
1
1
1
2
1
1
1
Tab.2: tabella di uscita

 

ANALISI DI MINIMALITA':
L'automa A proposto in Tab.1 e Tab.2 è il più semplice tra quelli che operano nel modo richiesto, se risulta minimo. Quando ciò non sia vero, si deve individuare un automa equivalente in forma minima (Amin), procedendo nel modo seguente.
  • INDISTINGUIBILITA':  innanzitutto si può effettuare, per esempio per mezzo dell'algoritmo di Paull-Unger, un'analisi di indistinguibilità di A. Il risultato di questa analisi è una partizione dell'insieme di stato X={1, 2, ..., n} in classi di indistinguibilità C1, C2, ...,Cnrid. Se ogni classe Ci è costituita da un solo elemento, allora nrid=n. In questo caso non esistono coppie di stati indistinguibili e l'automa è in forma ridotta (A=Arid). Se invece nrid<n l'automa ammette un automa equivalente in forma ridotta Arid, costituito da nrid stati. Questo automa è facilmente determinabile eliminando tutti gli stati, ad eccezione di uno scelto a caso, di ogni classe di indistinguibilità contenente almeno due stati. Il risultato di questa analisi è quindi in ogni caso un automa Arid in forma ridotta.
  • RAGGIUNGIBILITA': dato che all'istante iniziale l'automa Arid (con insieme di stato Xrid) è in un particolare stato di riposo (i=17 nel caso specifico), si deve determinare l'insieme Xragg degli stati raggiungibili dallo stato di riposo. Se Xragg coincide con Xrid tutti gli stati sono raggiungibili e pertanto Arid è in forma minima (Amin=Arid). Se invece Xragg è contenuto in Xrid si possono eliminare da Xrid tutti gli stati non raggiungibili ottenendo così un automa di dimensioni nmin<nrid. Tale automa, che ha come insieme di stato l'insieme Xragg, è l'automa Amin cercato.
APPLICAZIONE PRECEDENTE  APPLICAZIONE SUCCESSIVA