Macchine a stati finiti

Recentemente ci sono stati alcuni post su Ok, Panico che riguardavano le espressioni regolari, (RE). Mi sono detto che forse è il caso di fare una serie di post un pochino teorici sull’argomento, se ve la sentite. Ve la sentite? Ma sì, dai. Cominciamo da lontano, (anche se non troppo).

Un esempio di automa

Una macchina a stati finiti (o automa a stati finiti) è un aggeggio matematico-informatico che può aiutarci a descrivere alcuni semplici sistemi automatici. Per spiegarvi in pratica di cosa si tratta, parto come al solito da un esempio pratico: il sistema d’accesso al mio palazzo.

Il portone del palazzo dove abito, come quasi tutti i palazzi di Parigi, si apre quando si inserisce il codice alfanumerico corretto su una tastiera. La tastiera permette l’inserimento delle cifre 0-9, e delle lettere A e B. Un tipico codice contiene 5 caratteri, per esempio 12A45. Se si inserisce il codice corretto la porta si apre, altrimenti niente. Se sbagliate qualche cifra potete sempre ripartire da capo. Ad esempio, se sbagliate e premete 23 come prime due cifre, potere ricominciare da capo immediatamente, e quindi la porta si aprirà anche con la sequenza 2312A45, l’importante è che gli ultimi 5 caratteri siano corretti.

Come è implementato il circuito elettronico che regola l’apertura della porta? Esso riceve i caratteri, uno alla volta, e appena ha riconosciuto la sequenza giusta apre la porta. Quindi, il circuito deve ricordarsi la storia passata. Vediamo come può farlo efficacemente facendo un piccolo diagramma “a palle”:

macchina.png

Figure 1: Macchina a stati per l’apertura del portone con un codice

Ogni “palla” rappresenta uno stato del sistema. Inizialmente il sistema si trova nello stato S0, e aspetta i nostri comandi. Ogni comando che arriva può causare una “transizione di stato” che viene rappresentata da una freccia (o più precisamente, un arco orientato). Ho indicato in nero le transizioni “buone” per noi, mentre ho indicato in rosso le transizioni che ci fanno “tornare indietro” perché abbiamo sbagliato il codice. Per aprire la porta a partire dallo stato S0 dobbiamo fare uno dei percorsi con gli archi “neri”. Inoltre, ho colorato di verde la “palla” corrispondente allo stato che vogliamo raggiungere.

Ad esempio, se il sistema è nello stato S0 e premiamo il tasto ‘1’, il sistema si porta nello stato S1, altrimenti resta nello stato S0. Se il sistema si trova nello stato S3, abbiamo fatto la metà dello sforzo: se premiamo ancora il tasto ‘4’ andiamo avanti, se facciamo un errore torniamo allo stato S0, e infine se premiamo ‘1’ andiamo direttamente nello stato S1 perché questo potrebbe essere l’inizio di una nuova sequenza corretta.

Sembra complicato? In realtà la rappresentazione grafica è un pochino complicata da disegnare e da leggere per chi non è pratico (mentre è o dovrebbe essere pane per i denti di ogni informatico). La figura che vedete si chiama “grafo orientato”, e come potete immaginare c’è un’intera branca della matematica che se ne occupa.

Dato che abbiamo formalizzato il problema, potremmo fare delle analisi. Per esempio, è possibile dimostrare formalmente che:

  • da qualunque stato parto tra S0, S1, S2, S3, S4, digitando il codice giusto arrivo in S5;
  • che non c’è nessun altro modo per raggiungere S5.

In altre parole, possiamo dimostrare che il sistema funziona come volevamo: basta enumerare tutti i possibili casi.

Macchine a stati finiti

Le macchine a stati finiti sono utilizzate in moltissimi campi dell’ingegneria, dall’elettronica all’informatica, e sono state studiate per molti anni. Sono infatti alla base della teoria dell’informazione.

Si chiamano macchine o automi perché all’inizio furono applicate alla meccanica. D’altronde, i primi computer erano meccanici (la pascalina, la macchina analitica di Babbage…), e in molti casi servivano ad automatizzare dei compiti ripetitivi, da cui il nome di automi (in inglese si usa la parola latina automaton al singolare, e automata al plurale). Sono “a stati finiti” perché il numero di stati (le palle nel disegno) sono in numero finito.

Quest’ultima cosa è importante. Il fatto che gli stati siano finiti ci permette di controllare tutti i possibili percorsi nel grafo, ma ci dice anche che queste macchine non sono poi così tanto potenti … ma ne riparleremo più avanti.

La macchina che vi ho presentato è un riconoscitore, perché il suo scopo è di riconoscere una sequenza di input. Le macchine a stati finiti possono essere usati anche per scopi di controllo: si può complicare la notazione permettendo la possibilità di dare dei “comandi”. Ad esempio una macchina a stati finiti può essere utilizzata per leggere dei valori di temperatura e dei valori orari, e comandare l’accensione o lo spegnimento di una caldaia. In quel caso si parla di sistema ibrido ed è l’argomento di cui mi sto occupando recentemente nelle mie ricerche.

Macchine a stati finiti possono essere utilizzate per implementare il sistema di navigazione dei menu del vostro televisori; e ancora, Emacs, il mio editor preferito, usa gli automi a stati finiti per riconoscere sequenze di pressione dei tasti per comandi complicati; e lo stesso fa l’editor Vim. Insomma, dovunque ci sia uno “stato” in base al quale bisogna fare cose diverse, si possono utilizzare gli automi.

In questa mini-serie di post, noi ci focalizzeremo solo sulle macchine riconoscitrici: lo scopo è riconoscere se una sequenza in input è corretta. Se lo è, l’automa termina su uno stato di “accettazione” (nell’esempio in figura, lo stato S5 colorato in verde). Se la sequenza non è corretta, l’automa finisce su uno stato “non accettante” e “rifiuta” la sequenza.

Un esercizio

Per concludere questo primo post facciamo un esercizio. Supponiamo che i codici validi per aprire la porta siano 2: oltre a 12A45 c’è anche 22B48. Come facciamo a definire un unico automa che si occupi di aprire la porta in uno (e uno solo) dei due casi?

Proviamo subito.

seconda.png

Figure 2: Questa macchina non funziona

Senza stare a pensarci su, ho semplicemente aggiunto sugli archi le etichette del secondo codice.

Secondo voi, funziona bene questo secondo automa?

La risposta è niente affatto! Non posso semplicemente aggiungere le etichette sugli archi in questa maniera brutale, perché così facendo ho fatto un errore: all’uscita di S1 ci sono due archi che hanno l’etichetta ‘2’. Se il sistema è in S1 e viene premuto il tasto ‘2’ che succede? Si ricomincia ritorna in S1 oppure si va a S2?

Inoltre, anche supponendo di risolvere il problema togliendo l’etichetta ‘2’ dall’arco S1 -> S2, la porta si apre con molti più codici di prima! Ad esempio, il codice 12B48 apre la porta, e non dovrebbe.

Insomma, è tutto sbagliato. Volete pensare un po’ a risolvere il problema da soli? La prossima puntata vi riporto la soluzione e si continua la strada verso le espressioni regolari.

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

Commenti

Trackbacks

  • By Macchine a stati finiti – 2 | Ok, panico on 3 marzo 2014 at 19:04

    […] puntata. Cominciando risolvendo il problema della scorsa volta. Ricordiamo che i due codici che aprono la porta sono 12A45 e 22B48. Ecco il sistema corretto, dove […]

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: