Automi a Stati Finiti: fenomenologia, modelli e applicazioni (Moore e Mealy)
Prima di scrivere formule e tabelle, partiamo dall’osservazione dei fenomeni. Un semaforo che alterna i colori,
un display a sette segmenti che compone le cifre, un ascensore che risponde ai pulsanti: tutti
questi oggetti seguono regole semplici ma precise. Alcuni reagiscono solo all’ingresso corrente (come un interruttore),
altri devono anche ricordare cosa è accaduto poco prima (come il semaforo che “sa” quale luce viene dopo).
Per descrivere con rigore questi comportamenti usiamo gli automi a stati finiti: modelli che parlano di
stati, ingressi, uscite e transizioni. Studieremo due famiglie fondamentali:
gli automi di Moore, in cui l’uscita dipende dallo stato, e gli automi di Mealy,
in cui l’uscita dipende dalla coppia (stato, ingresso). A fare da controcanto, i sistemi combinatori,
in cui l’uscita è determinata solo dagli ingressi correnti e non c’è memoria.
Idea chiave: dal “mondo fisico” (fenomeni osservabili) al “mondo formale” (diagrammi, tabelle, funzioni).
Prima comprendiamo cosa accade; poi lo traduciamo in un modello chiaro e riutilizzabile.
Esempio di Moore: controllore di sequenze luminose
Fenomenologia
Immaginiamo tre luci che si accendono a intermittenza secondo una sequenza prefissata. All’interno dei cerchi che
rappresentano le luci scriviamo il colore: R (rosso), B (blu), V (verde),
G (giallo), N (nero/spento). A intervalli di tempo regolari il sistema “avanza” di una posizione
nella sequenza. Possiamo percorrere la sequenza nei due versi: A (avanti) e I (indietro),
secondo un segnale esterno di controllo. Come in un semaforo reale, un comando Stop spegne tutto (le luci
diventano “nere”) e un comando Start riavvia il ciclo dalla prima configurazione.
Nel diagramma a stati, ogni cerchio è uno stato con le tre uscite luminose. Dal centro partiamo con lo
stato iniziale Spento. Alla ricezione di Start passiamo a Stato 1 (prima terna).
Da lì, a ogni intervallo, una transizione di stato ci porta allo stato successivo o precedente in funzione di
A o I. Se arriva Stop, torniamo allo stato Spento.
Modello formale (Moore)
Regole (totali, con priorità implicita): Stop spegne sempre; Start da Spento avvia il ciclo; A scorre in avanti; I scorre indietro; da Spento, A/I non hanno effetto.
Tabella di transizione
| Stato \ Ingresso | Start | Stop | A | I |
|---|---|---|---|---|
| Spento | S1 | Spento | Spento | Spento |
| S1 | S1 | Spento | S2 | S4 |
| S2 | S2 | Spento | S3 | S1 |
| S3 | S3 | Spento | S4 | S2 |
| S4 | S4 | Spento | S1 | S3 |
Tabella di uscita (Moore: dipende dallo stato)
| Stato | Luce 1 | Luce 2 | Luce 3 |
|---|---|---|---|
| Spento | N | N | N |
| S1 | R | R | B |
| S2 | V | B | G |
| S3 | G | B | R |
| S4 | B | G | V |
Osservazione didattica: questo è un modello sincrono (transizioni a intervalli fissati/clock). È
utile per collegare il modello all’hardware (flip-flop + logica combinatoria).
Confronto: sistema combinatorio (display a 7 segmenti)
Fenomenologia
Un display a sette segmenti compone le cifre accendendo alcune “barrette” luminose. Se accendiamo i segmenti giusti
vediamo un 0, un 1, un 2, e così via. Qui non serve “memoria del passato”: la cifra mostrata dipende solo dalla
combinazione di ingresso corrente (ad esempio il numero in BCD). È quindi un sistema combinatorio.
Modello formale (combinatorio)
Uscite attive-alte (1 = acceso, 0 = spento). Ingresso codificato in BCD (0–9).
| Cifra | a | b | c | d | e | f | g |
|---|---|---|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
| 2 | 1 | 1 | 0 | 1 | 1 | 0 | 1 |
| 3 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
| 4 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
| 5 | 1 | 0 | 1 | 1 | 0 | 1 | 1 |
| 6 | 1 | 0 | 1 | 1 | 1 | 1 | 1 |
| 7 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 8 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| 9 | 1 | 1 | 1 | 1 | 0 | 1 | 1 |
Accenno alle equazioni (BCD 4 bit: 
). Esempio di funzione minimizzata per il segmento a:
Per la classe: costruire mappe di Karnaugh e ricavare le altre funzioni b–g.
Esempio di Mealy: ascensore a 4 piani
Fenomenologia
Un ascensore risponde ai pulsanti dei piani: se siamo al 2° e premiamo 3, il motore riceve il comando “salire” finché
non raggiungiamo il 3°. Se premiamo 2 mentre siamo già al 2°, il comando è “fermo”. La cosa importante è che il
comando (uscita) non dipende solo dallo stato (piano attuale), ma anche dall’ingresso (pulsante premuto) in quel momento.
Perciò è un tipico automa di Mealy: l’uscita è etichettata sulla transizione.
Modello formale (Mealy)
Regola operativa: se il target è maggiore dello stato → sali (S) e incrementa di un piano; se minore → scendi (G) e decrementa di un piano; se uguale → fermo (F).
Tabella unica (formato “prossimo/uscita”)
| Stato \ Ingresso | 1 | 2 | 3 | T |
|---|---|---|---|---|
| 1 | 1/F | 2/S | 2/S | T/G |
| 2 | 1/G | 2/F | 3/S | 1/G |
| 3 | 2/G | 2/G | 3/F | 2/G |
| T | 1/S | 1/S | 1/S | T/F |
Moore vs Mealy (in una frase)
Moore: l’uscita è funzione dello stato (stabile tra un tick e l’altro).
Mealy: l’uscita è funzione di stato e ingresso (reagisce già sulla transizione).
Esercizi
- Scrivi la definizione formale di un automa di Moore e di un automa di Mealy (insiemi, funzioni e stato iniziale).
- Per il controllore di luci (Moore), disegna il diagramma a stati e verifica la tabella di transizione proposta.
- Per il display a 7 segmenti, costruisci le mappe di Karnaugh per i segmenti b, c e g e ricava le funzioni minimizzate (BCD).
- Per l’ascensore (Mealy), aggiungi una logica di “richieste in coda” (memoria delle chiamate) e discuti come cambia il modello.
- (V/F) L’ascensore è Moore; è combinatorio; è senza memoria; è sequenziale.
Soluzione lampo: Moore ❌, combinatorio ❌, senza memoria ❌, sequenziale ✅.