Automi: la serratura a combinazione

A. Costantini | (la videolezione) Immaginiamo di avere una serratura a combinazione, cioè una serratura che provoca l’apertura di un dispositivo una volta che sia stata prodotta la giusta combinazione di simboli.  E’ noto che la costruzione di un modello per un sistema comporta sempre delle semplificazioni. In questo esempio introduciamo ulteriori semplificazioni per rendere più semplice l’analisi del sistema stesso. Immaginiamo di avere un tastierino con quattro pulsanti: uno corrisponde al carattere “A”, uno ad “F”, uno ad “L” e l’altro ad “S” (ovviamente, nella realtà si potrà pensare ad un tastierino con molti più pulsanti). Immaginiamo poi una serratura che si aprirà nel momento in cui venga digitata la parola “ALFA” . Ovviamente, non è detto che la parola debba essere necessariamente di quattro caratteri o che debba avere per forza di senso compiuto: con quei quattro caratteri si possono costruire moltissime sequenze di varie lunghezze. L’automa in questione è conosciuto come “riconoscitore di sequenza”. Immaginiamo, al solito, di essere nello stato iniziale X0 e di cominciare da qui a produrre la sequenza di caratteri che eventualmente provocherà l’apertura della serratura. Se nello stato X0 premiamo il tasto “A”, la macchina va nello stato X1 per ricordarsi che è iniziata una possibile giusta sequenza (“A” potrebbe essere la prima lettera della parola corretta). Rimane in X0, invece, se si preme un qualsiasi tasto diverso da “A” (la parola è sicuramente errata). Se in X1 e premiamo nuovamente “A” la macchina rimane in X1 (la nuova “A” potrebbe essere l’inizio di una sequenza corretta), se invece premiamo “S” oppure “F” si ritorna in X0, perché la parola è sicuramente errata e il processo deve ricominciare. Se in X1 si preme la lettera “L”, il sistema va nello stato X2, perché “A” ed è “L” sono le prime due lettere della parola corretta e deve ricordare che sono state inseriti due caratteri corretti. Se in X2 si preme un'altra “A” , l’automa ritorna in X1 (la “A” potrebbe essere l'inizio di una parola corretta). Se invece si preme “L” oppure “S” il sistema torna nello stato iniziale, perché la parola è sicuramente sbagliata. Se nello stato X2 si preme il tasto “F”, la macchina andrà nello stato X3 per ricordarsi, che sono state inserite tre lettere corrette: “A”, “L” ed “F”. Se in X3 si preme un'altra “A”, si ha il ritorno in X0 e la serratura si apre. Se invece siamo in X3 si preme un qualsiasi altro carattere, ritorniamo in X0 senza l’apertura della serratura e ricomincia il processo da capo. In definitiva, questo automa riconosce la sequenza “ALFA” e ogni volta che premiamo un tasto nella giusta sequenza avanza di uno stato. Quando si preme un tasto sbagliato, la macchina ritorno nello stato X0, tranne quando si preme il carattere “A”, perché quel carattere potrebbe essere l'inizio di una sequenza corretta.