Macchine a stati finiti – 2

Seconda puntata. Cominciamo risolvendo il problema della scorsa volta. Ricordiamo che i due codici che aprono la porta sono 12A45 e 22B48. Ecco il sistema corretto, dove per semplicità ho tolto tutti gli archi rossi: fate l’assunzione implicita che, ogni volta che premo un tasto sbagliato, il sistema vada automaticamente in S0

soluzione.png

Figure 1: Soluzione corretta del riconoscitore con due codici.

Anche così non è proprio semplicissimo, ma sono evidenti due file orizzontali di stati (anche perché le ho messe apposta così): quella superiore si occupa del primo codice 12A45, mentre quella inferiore si occupa del secondo codice 22B48. Inoltre, se mentre sto facendo il primo codice premo 2, il sistema passa a S2, e se mentre sto facendo il secondo codice premo 1, il sistema passa a S1, per cui ho tutte le frecce incrociate. Si può dimostrare (ma è abbastanza evidente) che questo automa riconosce solo i due codici voluti.

Implementazione

Come si implementano nella pratica questi automi? Non è affatto difficile, una volta che avete fatto il grafo. Se siete degli smanettoni elettronici, potete provare a costruire un semplice circuito digitale che riconosca i due codici. Innanzitutto serve una locazione di memoria per fare in modo di ricordarsi in quale stato siamo arrivati. Serve memorizzare 10 stati, per cui basta un registro a 4 bit. Poi naturalmente un tastierino alfanumerico che vi dia in output una sequenza di bit diversa per ogni tasto.

Poi si costruisce una bella tabella, con tante righe quanti sono gli stati, e con tante colonne quanti sono i possibili simboli in input. Nelle cella alla posizione (s,x) ci si mette lo stato in cui si finisce quando siamo nello stato s e riceviamo in input il simbolo x Per esempio, una cosa così:

Stato ‘1’ ‘2’ ‘4’ ‘5’ ‘8’ ‘A’ ‘B’ ‘*’
S0 S1 S2 S0 S0 S0 S0 S0 S0
S1 S1 S3 S0 S0 S0 S0 S0 S0
S2 S1 S4 S0 S0 S0 S0 S0 S0
S3 S1 S4 S0 S0 S0 S5 S0 S0
S4 S1 S4 S0 S0 S0 S0 S6 S0
               

Non avevo molta voglia di scriverla tutta a mano, ma naturalmente queste tabelle possono essere generate automaticamente. A questo punto avete sulle righe la rappresentazione in bit dello stato, e sulle colonne la rappresentazione in bit dell’input, e produrrete in output la rappresentazione in bit del prossimo stato. Questo è un semplice circuito combinatorio, e un elettronico dilettante dovrebbe sapere come sintetizzarlo, vero?

E quindi basta, abbiamo finito. E se vogliamo riprogrammarlo periodicamente con nuovi codici? Potete usare un Programmable Logic Device, ad esempio.

Avete la mano porcina per i lavori manuali, come il sottoscritto, e volete smanettare come un vero informatico che non si abbassa a toccare nient’altro che la tastiera di un PC? Potete implementare la stessa cosa in un qualunque linguaggio di programmazione. Lo stato viene memorizzato in una variabile, la tabella con uno switch-case oppure con una sequenza di if-then-else, oppure ancora con un array-bidimensionale. Non starò qui a spiegare per filo e per segno come fare, i nostri affezionati lettori di Ok, Panico sanno già tutto, vero?

Conclusioni parziali

Ma le espressioni regolari dove sono? La scorsa volta avevamo detto che avremmo parlato di RE, e fin qui abbiamo visto automi, macchine, latch e circuiti combinatori. Dove diavolo sono le RE?

In realtà le RE risolvono esattamente questo problema: come riconoscere una sequenza di caratteri in un testo (ed eventualmente fare delle sostituzioni). Quindi, i più sgamati di voi avranno probabilmente capito che gli automi e le RE sono collegati. Ma come?

La risposta alla prossima puntata!

Annunci
Post a comment or leave a trackback: Trackback URL.

Commenti

  • Stefano  On 4 marzo 2014 at 17:06

    non si dovrebbe andare da S3 a S4 con 2?

    • glipari  On 4 marzo 2014 at 17:49

      Si, bravo! Appena possibile correggo il bug cambiando la figura.

Trackbacks

  • By Linguaggi regolari | Ok, panico on 9 marzo 2014 at 10:24

    […] Oggi si va un po’ di più sulla teoria. Oh, prima o poi toccava farlo. Qui la scorsa puntata. […]

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...

%d blogger hanno fatto clic su Mi Piace per questo: