Gli automi

Un automa è un modello di calcolo molto semplice da utilizzare, adatto a descrivere un gran

numero di problemi di varia natura. Possiamo pensarlo come un dispositivo che legge una
stringa di input e la elabora secondo un banale meccanismo di elaborazione e una memoria
limitata, producendo delle uscite. Il tutto è rappresentabile graficamente in forma molto
intuitiva e immediata.

Ingressi AUTOMA Uscite

Stati interni

Possiamo trovare nella vita quotidiana molti esempi di automi: la lavatrice, la lavastoviglie, il
frullatore, il bancomat, i sistemi di controllo degli ascensori, i distributori automatici di
bevande, i distributori automatici di carburante, e anche oggetti più astratti come:
riconoscitori di sequenze, automi traduttori, decodificatori e così via.

Esempi

Per quanto detto, un automa è un sistema. Possiamo quindi introdurre la seguente

definizione.

Un automa è un sistema con le seguenti caratteristiche:

 dinamico: evolve nel tempo;
 invariante: la risposta del sistema ad una sollecitazione è la stessa
indipendentemente dall’istante di tempo in cui è applicata;
 discreto nell’avanzamento e nelle interazioni: l’insieme dei tempi è discreto e il
sistema può essere analizzato in precisi istanti di tempo; le funzioni di transizione e
trasformazione sono discrete;
 gli insiemi degli ingressi e delle uscite sono composti da un numero finito di
elementi.

1
Un automa a stati finiti è un automa in cui l’insieme degli stati è composto da un numero
finito di elementi.
Per descrivere un automa a stati finiti A, utilizziamo un modello matematico composto dai
seguenti elementi:
I l'insieme degli ingressi (o input) che è in grado di leggere;
U l'insieme delle uscite (o output) che può produrre;
S l'insieme finito degli stati interni in cui può trovarsi;
f la funzione di transizione che fa passare da uno stato al successivo;
g la funzione di trasformazione che determina il valore delle uscite.

A= {I, U, S, f, g}

Esercizio 1 (svolto)
Un automa emette in uscita un biglietto dopo che sono state inserite due monete da 0,2 €.
L'automa funziona solo con monete da 0,2 €.
Individuare gli insiemi degli ingressi, delle uscite, degli stati.

Soluzione

Esercizi
ingressi e uscite

2
Un automa a stati finiti può essere rappresentato :
 mediante un diagramma degli stati (modello grafico)
 mediante una tabella di transizione (modello matematico)
 mediante un programma (modello logico).

Diagrammi degli stati

Il diagramma (grafo) degli stati è una rappresentazione grafica di un automa costituita da

archi e nodi.
 I nodi rappresentano gli stati dell’automa. All’interno del nodo si scrive il nome dello
stato corrispondente.
 Gli archi rappresentano le relazioni di passaggio da uno stato all’altro. L’etichetta
sopra ogni arco ha la forma
Input/Output

cioè è formata dall’input che genera la transizione e dall’output che viene rilasciato a
seguito della transizione.
Per esempio, nella transizione

Moneta/Lattina
S1 S2

l’etichetta Moneta/Lattina significa che nello stato S2, quando si riceve una moneta, si
transita nello stato S1 emettendo in uscita una lattina.
 Lo stato iniziale è quello dal quale l’automa inizia a ricevere gli ingressi e a descrivere
il suo comportamento (elaborazione o esecuzione). Esso è rappresentato da una freccia
entrante.
 Gli stati finali sono particolari stati in cui si viene a trovare l’automa a termine di una
esecuzione che ha avuto successo. Sono individuati da un nodo (cerchio) con un doppio
bordo e vengono indicati solo negli automi per cui ciò ha significato.

Il diagramma degli stati è una rappresentazione grafica sia della funzione di transizione f
che della funzione di trasformazione g.

Esempio: automa distributore automatico di bibite

Descrizione
L’automa deve emettere in uscita una lattina di aranciata dopo che sono state inserite due
monete da 1 euro. L’automa funziona solo con monete da 1 euro.

Insiemi caratteristici dell’automa

 I = {Moneta}, con Moneta = moneta da 1 euro
 U= {Lattina, Niente}, con Lattina = lattina di aranciata
 S= {S1,S2}, con S1= (stato iniziale) in attesa dell’inserimento della prima moneta e
S2= in attesa dell’inserimento della seconda moneta

3
Diagramma degli stati

Ingresso/Uscita
Stato iniziale Stato normale

Moneta/Niente

S1 S2
Moneta/Lattina

Transizione di stato

Nell’arco che va dallo stato S1 allo stato S2, la dicitura “Moneta/Niente” indica che, in
corrispondenza dell’input “Moneta” è fornita l’uscita nulla (nessuna lattina).

Gli stati di un automa rappresentano i suoi stati di memoria. Un automa si trova in uno o in
un altro stato a seconda di ciò che è successo in precedenza. In base allo stato in cui si trova
e all’input che riceve l’automa stabilisce il suo comportamento.

Costruzione del diagramma degli stati

Individuiamo meglio i passi da seguire per arrivare alla costruzione del diagramma degli stati:
1. Analisi delle specifiche verbali e/o scritte
2. Formalizzazione
3. Sintesi con diagramma degli stati

Esempio: Automa ascensore

Descrizione dell’automa
Progettare la logica di un sistema capace di controllare un ascensore per una palazzina di tre
piani, con pulsantiera:

ALL
2
1
T

4
1. Analisi delle specifiche verbali e/o scritte

In questa fase si analizzano attentamente le specifiche che descrivono il progetto cercando di

trarre quante più possibili informazioni utili per il successivo passo della formalizzazione. In
questo caso è possibile dedurre gli insiemi caratteristici dell’automa:
 Ingressi: quattro, quanti i pulsanti sulla pulsantiera dell’ascensore
 Stati: tanti quanti sono i piani su cui può sostare l’ascensore
 Uscite: segnalazioni necessarie a comandare la salita o la discesa ai piani e in caso di
allarme

2. Formalizzazione

Si procede ora a codificare gli ingressi, gli stati e le uscite assegnando loro nomi più concisi:

Ingressi
1P Pulsante premuto per salire al primo piano
2P Pulsante premuto per salire al secondo piano
T Pulsante premuto per portarsi al piano terra
ALL Pulsante di allarme

Uscite
“Primo” Vai al primo piano
“Secondo” Vai al secondo piano
“Terra” Vai al piano terra
“SOS” Segnala condizione anomala

Stati
S0 Piano terra
S1 Primo piano
S2 Secondo piano
S3 Stato di allarme

3. Sintesi con diagramma degli stati

Cominciamo a progettare il diagramma a partire dallo stato iniziale S0. Nel caso in cui venga
premuto il pulsante 1P l’ascensore dovrà recarsi al primo piano ed emettere in uscita il
segnale “Primo”. Nel caso in cui venga premuto il pulsante 2P si avrà un analogo
comportamento. Nel caso, poi, in cui si prema il pulsante T il comando richiesto sarà
ininfluente e l’ascensore resterà a terra.

5
 T/ “Terra”

S0
1P/ “Primo” 2P/ “Secondo”

S2
S1

Terminata l’analisi relativa allo stato S0, possiamo completare il grafo procedendo allo stesso
modo sia per S1 che per S2.

T/ “Terra”
2P/ “Secondo”
S0 2P/ “Secondo”
1P/ “Primo”
1P/ “Primo”
S2
S1 T/ “Terra”
T/ “Terra”

2P/ “Secondo”

1P/ “Primo”

Va aggiunto inoltre lo stato S3 a cui si arriva premendo l’allarme e in cui si resta con qualsiasi
input successivo (stato finale), producendo il output il segnale di allarme.

Rappresentazione degli automi con le tabelle di transizione

Le tabelle (matrici) di transizione sono tabelle con un numero di righe pari al numero
degli stati dell’automa e un numero di colonne pari al numero dei diversi ingressi. Le celle
contengono una coppia formata dallo stato successivo e dall’uscita da emettere.

Consideriamo, ad esempio, l’automa distributore di bibite analizzato precedentemente. La

tabella di transizione che lo descrive è formata da due righe, poiché abbiamo due stati, e da
una sola colonna, poiché abbiamo un solo ingresso.

6
 Ingressi
Moneta
Stati
S1 S2/Niente
S2 S1/Lattina

La prima riga dice che quando ci si trova nello stato S1 (attesa prima moneta) e viene
inserita una moneta da 1 euro (Moneta) si passa allo stato S2 senza emettere in uscita una
lattina. Quando, invece, ci si trova nello stato S2 (attesa seconda moneta) e viene inserita
una moneta da 1 euro (Moneta), si passa allo stato iniziale S1 e questa volta si emette una
lattina.

Si consideri ora una seconda versione di tale automa.

Esempio: Automa distributore automatico di bibite – seconda versione

Descrizione
L’automa deve emettere in uscita una lattina di aranciata dopo che sono state inserite due
monete da 1 euro oppure una moneta da 2 euro. L’automa funziona solo con monete da 1
euro e da 2 euro e non fornisce resto.

Insiemi caratteristici
I = {Moneta1, Moneta2}
Moneta1 = è stata inserita una moneta da 1 euro
Moneta2 = è stata inserita una moneta da 2 euro

U = {Lattina, Moneta2, Niente}

Lattina = viene restituita la lattina di aranciata
Moneta2 = viene restituita una moneta da 2 euro

S = {S1, S2}
S1 = (stato iniziale) si è in attesa dell’inserimento della prima moneta
S2 = si è in attesa dell’inserimento di una seconda moneta

Diagramma degli stati

Moneta2/Moneta2
Moneta1/Niente

S1 S2
Moneta1/Lattina

Moneta2/Lattina

7
Analisi del diagramma
Questa volta, a differenza dell’esempio precedente, vi sono archi che tornano allo stesso stato
di partenza. Nello stato S1, ad esempio, quando si inserisce direttamente una moneta da 2
euro si rimane nello stesso stato e si emette una lattina.
Nello stato S2, quando si inserisce una moneta da 2 euro la si restituisce, poiché è già stata
inserita una moneta da 1 euro e si rimane nello stesso stato. Ovviamente se non si hanno
altre monete da 1 euro il sistema non dà resto e rimane in questo stato senza restituire
alcuna lattina. In genere, a questo punto si percuote violentemente il distributore sperando
che rilasci comunque la sospirata lattina.
Da notare che Moneta2 è presente anche nell’insieme U delle uscite.

Tabella di transizione
La tabella di transizione che descrive l’automa è la seguente:

Ingressi Moneta1 Moneta2

Stati
S1 S2/Niente S1/Lattina
S2 S1/Lattina S2/Moneta2

La seconda riga, per esempio, dice che, quando ci si trova nello stato S2 (attesa seconda
moneta):
 Se viene inserita una moneta da 1 euro (Moneta1) si passa allo stato S1 e si emette in
uscita una lattina.
 Se viene inserita una moneta da 2 euro (Moneta2), la si restituisce e si rimane nello
stesso stato in attesa di una moneta da 1 euro.

Esercizi
diagramma stati

Esercizi tabella di
transizione

Esercizi
riassuntivi