Automi di Moore e Mealy: differenze, conversioni e dieci esercizi svolti

Un sistema digitale non si limita a ricevere dati e produrre risposte: spesso deve ricordare gli eventi precedenti, riconoscere la propria situazione e scegliere quale comportamento adottare in seguito. Una macchina a stati finiti descrive proprio questo tipo di sistema, rappresentandone il funzionamento attraverso un insieme limitato di stati, gli input possibili e le transizioni che collegano uno stato all’altro.

Gli automi di Moore e di Mealy sono due modi di associare un output al comportamento della macchina. Nel modello di Moore l’uscita dipende dallo stato attivo; nel modello di Mealy dipende dallo stato e dall’input corrente. La differenza si riassume in due funzioni, ma le conseguenze si vedono nella sequenza degli output, nella costruzione dei diagrammi e nel momento in cui una risposta può essere prodotta.

Un semaforo che mostra il rosso perché si trova nella fase di arresto è un esempio intuitivo di comportamento Moore. Un rilevatore che segnala il riconoscimento di una sequenza proprio quando arriva l’ultimo bit può essere rappresentato in modo naturale con una macchina Mealy. Questi esempi non stabiliscono quale modello sia sempre migliore: aiutano, invece, a individuare se l’uscita descrive una condizione del sistema oppure la sua risposta a un input.

Di seguito troviamo un richiamo teorico, le regole essenziali per convertire una rappresentazione nell’altra e dieci esercizi con soluzione commentata. Negli esempi in cui la sequenza temporale è importante, viene dichiarato se si conta anche l’output dello stato iniziale oppure soltanto quello prodotto dopo ciascun input.

Richiamo teorico: stati, input e output

Una macchina a stati finiti deterministica può essere descritta mediante un insieme di stati [math]Q[/math], un alfabeto di input [math]\Sigma[/math], un insieme di output [math]\Delta[/math], uno stato iniziale [math]q_0[/math], una funzione di transizione [math]\delta[/math] e una funzione di output. Per una macchina completa, la funzione di transizione è:

[math]\delta: Q \times \Sigma \to Q[/math]

Essa indica quale stato viene raggiunto quando la macchina, trovandosi in uno stato [math]q[/math], riceve un simbolo [math]x[/math]. Se la specifica non definisce una transizione per ogni coppia stato-input, si parla di macchina parziale e [math]\delta[/math] non è definita per tutte le coppie.

La differenza tra Moore e Mealy riguarda la funzione di output, che viene indicata qui con [math]\lambda[/math].

Automa di Moore

In una macchina di Moore l’output dipende esclusivamente dallo stato corrente:

[math]\lambda: Q \to \Delta[/math]

A ogni stato è associato un solo output. Se la macchina si trova nello stato [math]q[/math], l’uscita è [math]\lambda(q)[/math], indipendentemente dal simbolo che ha causato l’ingresso in quello stato o che verrà elaborato successivamente.

Nei diagrammi l’output compare di norma all’interno dello stato oppure accanto al suo nome. Una notazione come [math]q/0[/math] significa che, quando lo stato attivo è [math]q[/math], l’uscita vale 0. Le transizioni riportano gli input che provocano il passaggio da uno stato all’altro.

Automa di Mealy

In una macchina di Mealy l’output dipende dallo stato corrente e dall’input elaborato:

[math]\lambda: Q \times \Sigma \to \Delta[/math]

Una transizione determina quindi sia lo stato successivo sia l’output prodotto. Nei diagrammi si usa normalmente la notazione [math]input/output[/math], per esempio [math]a/1[/math]: leggendo l’input [math]a[/math], la macchina emette 1 e segue la transizione indicata.

Confronto tra i due modelli

Il numero di stati non costituisce una regola assoluta a favore di uno dei due modelli. Mealy può rappresentare con una transizione un output che Moore associa a uno stato dedicato, ma una conversione concreta dipende dalla funzione di output, dalle transizioni e dalla convenzione usata per il valore iniziale.

Output e convenzioni temporali

Consideriamo una macchina di Moore nello stato iniziale [math]q_0[/math] e una sequenza di [math]n[/math] input. Se registriamo l’output dello stato iniziale e quello associato allo stato dopo ogni input, la sequenza contiene [math]n+1[/math] valori. Se invece iniziamo a osservare soltanto dopo il primo input, i valori osservati sono [math]n[/math]. La differenza dipende da ciò che si vuole contare, non da un cambiamento nella definizione della macchina.

Per una macchina Mealy, si associa normalmente un output a ogni input elaborato, perciò una sequenza di [math]n[/math] input produce [math]n[/math] output. Prima del primo input non è necessariamente previsto un output. Quando si confrontano due automi, è importante specificare se l’output iniziale fa parte del comportamento da preservare.

Anche la relazione con il clock va descritta senza trasformare una convenzione di implementazione in una proprietà universale. In una comune realizzazione sincrona, lo stato è memorizzato e aggiornato sul fronte del clock. Un’uscita Moore dipende dallo stato registrato, mentre un’uscita Mealy può dipendere anche dal valore corrente dell’ingresso attraverso la logica combinatoria. Mealy può quindi consentire una risposta entro il ciclo corrente, dopo il ritardo di propagazione della logica, senza attendere un ulteriore aggiornamento dello stato.

Questo non significa che l’uscita Mealy cambi senza ritardo o che sia sempre preferibile quando serve una risposta rapida. Un ingresso asincrono o rumoroso deve essere gestito con le tecniche adeguate, come sincronizzazione e filtraggio; anche i ritardi, i glitch e i requisiti di sicurezza dipendono dalla realizzazione concreta. La scelta del modello descrive il rapporto logico tra stato, input e output, mentre il progetto hardware deve rispettare vincoli temporali e operativi ulteriori.

Conversione da Moore a Mealy

Per convertire una macchina Moore in una macchina Mealy mantenendo la corrispondenza degli output dopo ciascun input, si associa a ogni transizione l’output dello stato di destinazione. Se in Moore abbiamo:

[math]q_i \xrightarrow{x} q_j[/math]

con [math]\lambda(q_j)=y[/math], la transizione corrispondente in Mealy diventa:

[math]q_i \xrightarrow{x/y} q_j[/math]

La scelta dello stato di destinazione è essenziale: dopo aver elaborato [math]x[/math], la macchina Moore si trova in [math]q_j[/math] e presenta l’output [math]\lambda(q_j)[/math]. Trasferendo quel valore sull’arco Mealy si conserva quindi l’output successivo a quell’input.

La conversione descritta non trasferisce automaticamente l’output Moore osservato prima del primo input, perché una macchina Mealy standard produce l’output durante l’elaborazione di una transizione. Se anche il valore iniziale deve essere riprodotto, occorre dichiarare una convenzione specifica oppure aggiungere una transizione o uno stato iniziale dedicato.

Conversione da Mealy a Moore

La conversione da Mealy a Moore può richiedere la creazione di copie di alcuni stati. Il motivo è che una macchina Moore assegna un solo output a ciascuno stato, mentre in una macchina Mealy transizioni diverse possono produrre output diversi pur raggiungendo lo stesso stato.

Per ogni stato Mealy si esaminano gli output delle transizioni entranti. Se tutte le transizioni che raggiungono quello stato producono lo stesso output, è sufficiente una sola copia. Se le transizioni entranti producono valori diversi, si crea una copia per ciascun valore da rappresentare, associando a ogni copia l’output corrispondente. Da ciascuna copia si riportano le transizioni uscenti del corrispondente stato Mealy, indirizzandole verso la copia dello stato di destinazione determinata dall’output dell’arco.

Nella costruzione standard, il numero delle copie non supera [math]|Q|\times|\Delta|[/math], perché ciascuno stato può richiedere al massimo una copia per ogni output possibile. Questo limite descrive il numero massimo di coppie stato-output nella costruzione, non il numero di stati che ogni conversione deve necessariamente avere. Le copie irraggiungibili possono inoltre essere eliminate. Se si vuole preservare anche un comportamento iniziale prima del primo input, può servire una gestione specifica dello stato iniziale, che va conteggiata a parte e dichiarata.

Applicazioni pratiche delle macchine a stati finiti

Una macchina a stati finiti è utile quando un dispositivo o un programma deve reagire in modo diverso a seconda della fase in cui si trova e degli eventi che riceve. Nelle applicazioni reali il modello rappresenta spesso il controllo logico di una parte del sistema, mentre sensori, attuatori, basi di dati e algoritmi di pianificazione svolgono compiti ulteriori. Gli esempi seguenti mostrano come identificare stati, input e output senza confondere il modello con l’intera implementazione.

Lettore di badge e varco d’accesso

Un varco elettronico può trovarsi negli stati CHIUSO, IN_ATTESA_DI_APERTURA, APERTO e IN_BLOCCO. Gli input comprendono la lettura di un badge valido o non valido, il rilevamento dell’apertura fisica del varco, la sua richiusura e la scadenza del tempo concesso per il passaggio. L’uscita associata allo stato CHIUSO mantiene attivo il blocco, mentre nello stato APERTO il comando abilita il passaggio; un segnale acustico o un messaggio di diniego può invece essere prodotto direttamente dalla transizione che riceve un badge non valido.

La parte che mantiene il blocco o indica la condizione corrente è rappresentabile naturalmente con Moore, mentre la risposta puntuale a una lettura non valida può essere descritta con Mealy. Un sistema reale deve inoltre gestire situazioni come un varco forzato o rimasto aperto, senza affidare la sicurezza alla sola macchina astratta.

Controllo di un ascensore

Un controllore semplificato può distinguere gli stati FERMO, IN_SALITA, IN_DISCESA, PORTE_IN_APERTURA e PORTE_APERTE. Le richieste dei passeggeri, il sensore che segnala il raggiungimento di un piano, il rilevamento di un ostacolo e il comando di chiusura costituiscono input; il motore, le porte e gli indicatori di piano sono esempi di output. Se il controllore si trova in IN_SALITA, per esempio, l’uscita comanda il movimento verso l’alto, mentre l’arrivo al piano previsto provoca la transizione verso la fase di apertura delle porte.

La macchina a stati chiarisce le fasi operative e le transizioni ammesse, ma la gestione di più richieste richiede anche una politica di pianificazione, e un impianto reale deve rispettare interblocchi e requisiti di sicurezza certificabili. Se si vuole distinguere ogni piano, lo stato deve includere anche la posizione; il numero di stati resta finito perché l’edificio ha un numero finito di piani.

Ciclo di una lavatrice

Una lavatrice può alternare le fasi SPENTA, RIEMPIMENTO, LAVAGGIO, RISCIACQUO, CENTRIFUGA e FINE_PROGRAMMA, con uno stato di ERRORE per condizioni anomale. Tra gli input figurano il programma scelto, il raggiungimento del livello d’acqua, la scadenza di un timer, l’apertura dello sportello e la richiesta di annullamento; gli output comandano valvole, pompa, motore e indicatori sul pannello.

Le uscite legate alla fase — per esempio aprire la valvola durante RIEMPIMENTO — si rappresentano in modo diretto con Moore. Un segnale che deve reagire alla pressione di un tasto o a un evento specifico può invece dipendere dalla transizione. Sensori analogici come temperatura e livello non sono di per sé stati finiti: il controllore li trasforma in condizioni discrete, per esempio “temperatura raggiunta” oppure “livello sufficiente”, prima di usarli come input della macchina.

Operazione allo sportello automatico

Un ATM può essere descritto mediante stati quali IN_ATTESA, CARTA_LETTA, VERIFICA_CODICE, SCELTA_OPERAZIONE, EROGAZIONE, RESTITUZIONE_CARTA e BLOCCO_TEMPORANEO. L’inserimento della carta, l’invio del PIN, l’esito della verifica, la selezione di un’operazione e il completamento dell’erogazione sono input o eventi che determinano i passaggi tra le fasi. La schermata corrente può dipendere dallo stato, mentre un messaggio di errore può essere emesso sulla transizione provocata da un PIN non valido.

Questa rappresentazione descrive il flusso dell’interazione, ma non sostituisce i controlli di autenticazione, la verifica dei fondi, la contabilizzazione e le misure che proteggono i dati della carta. Tali componenti devono cooperare con il controllore e avere specifiche proprie.

Connessione a un servizio di rete

Un protocollo di comunicazione può distinguere stati come DISCONNESSO, RICHIESTA_INVIATA, CONNESSO e CHIUSURA_IN_CORSO. La richiesta di connessione, la ricezione di una conferma, l’arrivo di dati, la richiesta di chiusura e la scadenza di un timeout sono esempi di input; le risposte del protocollo vengono spesso prodotte quando si verifica una transizione, perciò una macchina Mealy è una descrizione naturale di questa parte del comportamento.

In un protocollo concreto possono esistere contatori, numeri di sequenza e timer. Per rappresentarli con una FSM pura occorre limitarli a un insieme finito di valori oppure trattarli come variabili esterne associate agli stati; il diagramma rimane utile per rendere esplicite le fasi e i messaggi ammessi, senza pretendere di descrivere ogni dettaglio implementativo.

Accesso a un’applicazione e scadenza della sessione

Un’applicazione può gestire il flusso di accesso attraverso gli stati NON_AUTENTICATO, VERIFICA_IN_CORSO, AUTENTICATO, BLOCCATO e SESSIONE_SCADUTA. L’invio delle credenziali, l’esito della verifica, la richiesta di uscita e la scadenza del tempo di inattività sono eventi che provocano transizioni. L’interfaccia può mostrare le funzioni disponibili in base allo stato corrente, secondo una logica Moore, mentre il messaggio associato a un tentativo di accesso non riuscito può essere modellato come output Mealy.

Il numero di tentativi può essere rappresentato con stati distinti se il limite è prefissato, oppure con una variabile finita del controllore. La FSM descrive il flusso dell’interazione, ma non stabilisce se le credenziali siano corrette: la verifica spetta al componente di autenticazione e deve applicare le misure di protezione previste per il servizio.

Come ricavare una FSM da un caso reale

Per modellare un sistema conviene partire dalle situazioni che ne cambiano il comportamento, evitando di creare uno stato per ogni dettaglio interno. Gli stati devono distinguere le condizioni che producono risposte diverse; gli input rappresentano gli eventi o le condizioni discrete che possono verificarsi; gli output descrivono le azioni, i segnali o i messaggi generati. Dopo aver elencato questi elementi, si controlla che ogni coppia stato-input rilevante abbia una transizione definita e che la sequenza di uscite corrisponda alla temporizzazione richiesta.

La macchina a stati finiti non è sempre una rappresentazione completa dell’impianto o del software: grandezze continue, code di richieste e dati persistenti possono richiedere modelli aggiuntivi. È comunque uno strumento efficace per rendere esplicite le fasi operative, verificare che gli eventi siano gestiti e individuare passaggi mancanti prima di implementare il controllo.

Esercizi svolti

Termostato smart

Un termostato dispone di tre stati: SPENTO, RISCALDAMENTO e RAFFREDDAMENTO. Il display mostra rispettivamente OFF, HEAT e COOL in base allo stato attivo. I comandi di temperatura possono provocare il passaggio da uno stato all’altro, ma non modificano direttamente il valore mostrato mentre il termostato si trova in uno stato dato.

Quale modello rappresenta meglio il display?

• A. Mealy, perché l’output dipende dall’input.
• B. Moore, perché l’output dipende soltanto dallo stato.
• C. Moore, perché l’output dipende da input e stato.
• D. Mealy, perché l’output è scritto sugli archi.

Risposta corretta: B. In questo esempio la funzione di output associa un valore a ciascuno stato:

[math]SPENTO \mapsto OFF[/math]

[math]RISCALDAMENTO \mapsto HEAT[/math]

[math]RAFFREDDAMENTO \mapsto COOL[/math]

Gli input possono influenzare la funzione di transizione e determinare quale sarà lo stato successivo, ma non entrano direttamente nella funzione che stabilisce ciò che il display mostra. La rappresentazione Moore è quindi la più naturale per questa specifica. Se il display dovesse invece cambiare in risposta al pulsante premuto anche quando lo stato rimane lo stesso, sarebbe necessario considerare una funzione di output dipendente dall’input.

Domanda di riflessione: quale proprietà formale distingue i due modelli?

Chatbot di supporto

Un chatbot è rappresentato con una macchina Mealy il cui stato iniziale è [math]q_0[/math]. Le transizioni specificate sono:

[math]q_0 \xrightarrow{ciao/saluta} q_1[/math]

[math]q_1 \xrightarrow{problema/apri\_ticket} q_2[/math]

[math]q_2 \xrightarrow{grazie/chiudi} q_0[/math]

L’utente invia la sequenza di input ciao, problema, grazie. Quale sequenza di output viene prodotta?

• A. saluta, apri_ticket, chiudi
• B. apri_ticket, saluta, chiudi
• C. saluta, chiudi, apri_ticket
• D. Nessun output, perché si tratta di una macchina Moore.

Risposta corretta: A. In una macchina Mealy l’output è indicato sulla transizione, quindi per ogni input si segue l’arco corrispondente e si legge il valore che segue la barra. L’input ciao porta da [math]q_0[/math] a [math]q_1[/math] e produce saluta; problema conduce da [math]q_1[/math] a [math]q_2[/math] e produce apri_ticket; infine grazie riporta a [math]q_0[/math] con output chiudi.

Domanda di riflessione: nella notazione di una macchina Mealy, dove si indica l’output?

Semaforo pedonale di Moore

Un semaforo pedonale è rappresentato dai tre stati seguenti, nei quali il valore dopo la barra indica l’output:

[math]S_0/VERDE[/math]

[math]S_1/GIALLO[/math]

[math]S_2/ROSSO[/math]

Le transizioni sono [math]S_0 \xrightarrow{timer} S_1[/math], [math]S_1 \xrightarrow{timer} S_2[/math] e [math]S_2 \xrightarrow{pulsante} S_0[/math]. Lo stato iniziale è [math]S_0[/math]. Per la sequenza di input timer, timer, pulsante, timer, quale sequenza di output si ottiene includendo esplicitamente l’output iniziale?

• A. VERDE, GIALLO, ROSSO, VERDE, GIALLO
• B. GIALLO, ROSSO, VERDE, GIALLO
• C. VERDE, ROSSO, GIALLO, VERDE
• D. VERDE, GIALLO, VERDE, ROSSO, GIALLO

Risposta corretta: A. Prima di leggere gli input la macchina si trova in [math]S_0[/math], perciò il primo output è VERDE. Il primo timer porta a [math]S_1[/math] e l’output diventa GIALLO; il secondo timer conduce a [math]S_2[/math] e produce ROSSO; pulsante riporta a [math]S_0[/math] con output VERDE; l’ultimo timer porta nuovamente a [math]S_1[/math] con output GIALLO. Considerando lo stato iniziale, quattro input corrispondono a cinque valori osservati.

Domanda di riflessione: se si usasse una macchina Mealy, quale convenzione temporale andrebbe esplicitata nel confronto?

Allarme IoT e risposta durante il ciclo

Un sensore invia un bit che segnala una condizione di allarme. La specifica richiede che l’uscita possa dipendere dal valore 1 ricevuto durante il ciclo corrente, senza attendere che venga raggiunto un nuovo stato registrato al successivo fronte di clock. Quale rappresentazione è più naturale?

• A. Moore, perché l’output dipende dallo stato.
• B. Mealy, perché l’output può dipendere dall’input corrente.
• C. Moore, perché usa più stati.
• D. Mealy, perché non dispone di stati.

Risposta corretta: B. Una macchina Mealy può definire l’output in funzione della coppia stato-input [math](q,x)[/math], così che la logica combinatoria dell’uscita risponda all’ingresso corrente anche prima di un ulteriore aggiornamento dello stato. Nella realizzazione concreta la risposta arriva dopo il tempo di propagazione dei circuiti e deve rispettare i vincoli di sincronizzazione.

La scelta di Mealy, da sola, non rende un allarme più sicuro né garantisce che un segnale asincrono possa essere utilizzato direttamente. Se l’ingresso proviene da un sensore esterno al clock del sistema, il progetto deve prevedere le misure necessarie a gestire sincronizzazione, disturbi e possibili transitori.

Domanda di riflessione: quale parte del comportamento può dipendere direttamente dall’ingresso in una macchina Mealy?

Rilevatore sovrapposto della sequenza 101

Si vuole riconoscere la sequenza di bit 101 in un flusso, permettendo che le occorrenze si sovrappongano. Per esempio, nel flusso 10101 la sequenza compare due volte.

Quale affermazione descrive correttamente il confronto tra i due modelli?

• A. Mealy richiede sempre più stati di Moore.
• B. Moore può richiedere uno stato in più, perché l’output di riconoscimento deve essere associato a uno stato.
• C. Moore e Mealy hanno sempre lo stesso numero di stati.
• D. Moore non può riconoscere sequenze.

Risposta corretta: B.

Un rilevatore Mealy può essere costruito con tre stati: [math]S_0[/math] quando non è stato riconosciuto alcun prefisso utile, [math]S_1[/math] dopo aver letto il prefisso 1 e [math]S_{10}[/math] dopo aver letto 10. Le transizioni principali sono:

L’output 1 compare sulla transizione da [math]S_{10}[/math] con input 1, perché quel bit completa il pattern. Lo stato di destinazione è [math]S_1[/math], dato che la sequenza appena riconosciuta termina con 1 e quel suffisso può essere l’inizio di una nuova occorrenza.

Una macchina Moore equivalente per questa specifica può usare quattro stati: [math]M_0/0[/math], [math]M_1/0[/math], [math]M_{10}/0[/math] e [math]M_{101}/1[/math]. L’ultimo stato segnala il riconoscimento dopo il completamento della sequenza. Il confronto tre contro quattro vale per la costruzione descritta, con riconoscimento sovrapposto e output osservato secondo la convenzione propria di ciascun modello; non dimostra che Mealy richieda sempre meno stati.

Le transizioni della macchina Moore possono essere riassunte così:

La riga di [math]M_{101}[/math] conserva la sovrapposizione: dopo aver riconosciuto 101, il bit 0 lascia come suffisso utile 10, mentre il bit 1 lascia il suffisso 1. L’output 1 è associato allo stato [math]M_{101}[/math], perciò viene osservato quando la macchina raggiunge quello stato.

Domanda di riflessione: quale stato deve essere raggiunto dopo il riconoscimento di 101 se si vogliono consentire occorrenze sovrapposte?

Conversione da Moore a Mealy

Consideriamo una macchina di Moore con [math]\lambda(q_0)=0[/math], [math]\lambda(q_1)=1[/math] e [math]\lambda(q_3)=1[/math]. Dallo stato [math]q_3[/math] partono le transizioni [math]q_3 \xrightarrow{A} q_0[/math] e [math]q_3 \xrightarrow{B} q_1[/math]. Si vuole costruire una macchina Mealy che conservi gli output prodotti dopo ciascun input. Quali valori vanno associati ai due archi?

• A. [math]A/1[/math] e [math]B/1[/math]
• B. [math]A/0[/math] e [math]B/1[/math]
• C. [math]A/1[/math] e [math]B/0[/math]
• D. [math]A/\lambda(q_3)[/math] e [math]B/\lambda(q_3)[/math]

Risposta corretta: B. Quando viene letto [math]A[/math], la macchina Moore raggiunge [math]q_0[/math] e l’output associato al nuovo stato è [math]\lambda(q_0)=0[/math]. La transizione Mealy corrispondente è quindi [math]q_3 \xrightarrow{A/0} q_0[/math]. Con l’input [math]B[/math] la macchina raggiunge [math]q_1[/math], il cui output è 1, perciò la transizione diventa [math]q_3 \xrightarrow{B/1} q_1[/math].

L’output dello stato di partenza [math]q_3[/math] non va copiato su tutti gli archi uscenti: la conversione conserva l’output dello stato raggiunto dopo l’elaborazione dell’input. Se occorre conservare anche l’output iniziale di [math]q_3[/math] prima del primo input, la convenzione deve essere aggiunta alla specifica, perché un normale arco Mealy non produce un valore prima che si verifichi una transizione.

Domanda di riflessione: perché si usa l’output dello stato di destinazione e non quello di partenza?

Conversione da Mealy a Moore

Consideriamo una macchina Mealy con stato iniziale [math]q_0[/math] e transizioni:

[math]q_0 \xrightarrow{a/0} q_0[/math]

[math]q_0 \xrightarrow{b/1} q_1[/math]

[math]q_1 \xrightarrow{a/0} q_0[/math]

[math]q_1 \xrightarrow{b/0} q_1[/math]

Si vuole riprodurre l’output prodotto dopo ogni input. Che cosa occorre fare per rappresentare [math]q_1[/math] nella macchina Moore?

• A. Lasciarlo come unico stato con output 0.
• B. Lasciarlo come unico stato con output 1.
• C. Rappresentarlo con copie distinte, perché le transizioni entranti producono output diversi.
• D. Eliminarlo, perché una macchina Mealy non contiene stati.

Risposta corretta: C.

Lo stato [math]q_1[/math] è raggiunto dalla transizione [math]q_0 \xrightarrow{b/1} q_1[/math], che produce output 1, ma anche dalla transizione [math]q_1 \xrightarrow{b/0} q_1[/math], che produce output 0. Nella macchina Moore questi due risultati devono essere rappresentati con stati diversi, poiché un singolo stato non può avere contemporaneamente due output.

Possiamo quindi introdurre [math]q_1^{(1)}/1[/math] e [math]q_1^{(0)}/0[/math]. Lo stato [math]q_0[/math] ha invece output 0 su tutte le transizioni entranti dell’esempio e può essere rappresentato da [math]q_0^{(0)}/0[/math]. Le transizioni in uscita dalle copie di [math]q_1[/math] riproducono quelle di [math]q_1[/math] nella macchina originale: con input [math]a[/math] si raggiunge [math]q_0^{(0)}[/math], mentre con input [math]b[/math] si raggiunge [math]q_1^{(0)}[/math]. L’uscita dalla copia [math]q_0^{(0)}[/math] segue le transizioni definite per [math]q_0[/math], raggiungendo [math]q_0^{(0)}[/math] con [math]a[/math] e [math]q_1^{(1)}[/math] con [math]b[/math].

Per confrontare le due macchine si contano qui gli output successivi agli input; [math]q_0^{(0)}[/math] è scelto come stato iniziale Moore e il suo output prima del primo input non viene considerato parte della sequenza Mealy da riprodurre.

Domanda di riflessione: perché la presenza di più transizioni entranti non comporta sempre la duplicazione dello stato?

Controllo industriale con input rumoroso

In un controllo industriale sincrono un ingresso può oscillare per un breve intervallo a causa di disturbi elettrici. La specifica richiede che l’uscita non dipenda direttamente da quelle variazioni momentanee, ma resti associata allo stato memorizzato e aggiornato dal clock. Quale modello è più naturale per descrivere questa relazione?

• A. Mealy, perché combina input e stato e reagisce sempre subito.
• B. Moore, perché l’output dipende dallo stato e non direttamente dall’input corrente.
• C. Mealy, perché utilizza meno stati.
• D. Moore, perché non ha transizioni.

Risposta corretta: B. In una macchina Moore l’uscita dipende dal solo stato. Se il comportamento desiderato è che il segnale di uscita segua uno stato registrato e non il valore istantaneo dell’ingresso, Moore rappresenta direttamente tale vincolo. In una macchina Mealy, invece, il valore corrente dell’ingresso può entrare nella logica combinatoria che determina l’uscita.

Questo confronto non significa che Moore renda automaticamente sicuro un impianto o che Mealy sia inadatto a sistemi critici. La progettazione deve trattare sincronizzazione degli ingressi, filtraggio, metastabilità, temporizzazione, logica combinatoria e requisiti di sicurezza secondo il contesto applicativo.

Domanda di riflessione: perché un progettista potrebbe comunque preferire Mealy in un sistema reattivo?

Semaforo pedonale con pulsante

Un semaforo per veicoli attraversa tre fasi: VEICOLI_VERDI, VEICOLI_GIALLO e VEICOLI_ROSSO. Il segnale pedonale è ROSSO_PED nelle prime due fasi e VERDE_PED nella terza. La pressione del pulsante può influenzare le transizioni tra le fasi, ma non cambia direttamente il segnale pedonale mentre la fase corrente resta invariata.

Quale rappresentazione descrive meglio il segnale pedonale?

• A. Moore, perché l’output è associato agli stati.
• B. Mealy, perché l’output compare soltanto sulla transizione provocata dal pulsante.
• C. Moore, perché l’output è associato agli archi.
• D. Mealy, perché l’output è associato agli stati.

Risposta corretta: A.

La funzione di output associa ROSSO_PED agli stati VEICOLI_VERDI e VEICOLI_GIALLO, mentre associa VERDE_PED allo stato VEICOLI_ROSSO. L’input del pulsante può condizionare la funzione di transizione, ma non fa parte della funzione di output descritta. La rappresentazione Moore mantiene quindi il segnale pedonale legato alla fase attiva.

Se la specifica imponesse invece che il segnale cambiasse direttamente in risposta alla pressione del pulsante, senza attendere l’ingresso in uno stato con un diverso output, una rappresentazione Mealy potrebbe esprimere più direttamente quel comportamento. Sarebbe comunque possibile modellare lo stesso effetto con Moore introducendo uno stato dedicato, purché la temporizzazione desiderata sia rispettata.

Domanda di riflessione: se il verde pedonale dipendesse direttamente dalla pressione del pulsante, quale funzione di output potrebbe rappresentarlo?

Macchinetta distributrice: conversione da Mealy a Moore

Una macchinetta distributrice è modellata con tre stati che rappresentano il credito: [math]q_0[/math] corrisponde a 0 euro, [math]q_1[/math] a 1 euro e [math]q_2[/math] a 2 euro. Gli input sono [math]M[/math], moneta da 1 euro; [math]E[/math], comando di erogazione; e [math]R[/math], reset. La macchina iniziale è [math]q_0[/math] e le transizioni considerate sono:

[math]q_0 \xrightarrow{M/0} q_1[/math]

[math]q_1 \xrightarrow{M/0} q_2[/math]

[math]q_2 \xrightarrow{E/1} q_0[/math]

[math]q_0 \xrightarrow{R/0} q_0[/math]

[math]q_1 \xrightarrow{R/0} q_0[/math]

[math]q_2 \xrightarrow{R/0} q_0[/math]

La specifica è intenzionalmente parziale: le combinazioni non elencate, cioè [math](q_0,E)[/math], [math](q_1,E)[/math] e [math](q_2,M)[/math], non fanno parte del comportamento considerato. Si vogliono riprodurre gli output Mealy dopo ogni input, senza imporre una corrispondenza per un output precedente al primo input. Quanti stati richiede la costruzione Moore descritta?

• A. Tre, perché la macchina originale contiene tre stati.
• B. Quattro, perché [math]q_0[/math] deve essere rappresentato con output diversi.
• C. Sei, perché ogni stato deve essere duplicato.
• D. Nove, perché ogni stato richiede una copia per ciascun output possibile.

Risposta corretta: B.

Esaminiamo gli output degli archi entranti nei tre stati. [math]q_1[/math] è raggiunto soltanto da [math]q_0 \xrightarrow{M/0} q_1[/math], mentre [math]q_2[/math] è raggiunto soltanto da [math]q_1 \xrightarrow{M/0} q_2[/math]; per ciascuno basta quindi una copia con output 0.

[math]q_0[/math] è invece raggiunto sia da [math]q_2 \xrightarrow{E/1} q_0[/math], sia dalle transizioni di reset, che producono output 0. Servono perciò due copie, [math]q_0^{(1)}/1[/math] e [math]q_0^{(0)}/0[/math]. Insieme a [math]q_1^{(0)}/0[/math] e [math]q_2^{(0)}/0[/math], la costruzione contiene quattro stati. Lo stato iniziale Moore può essere [math]q_0^{(0)}[/math], perché l’output che precede il primo input non fa parte della sequenza Mealy che si è scelto di riprodurre.

Le transizioni in uscita dalle copie seguono la macchina originale, indirizzando ogni arco verso la copia determinata dal suo output. Per esempio, dalla copia [math]q_2^{(0)}[/math] l’input [math]E[/math] porta a [math]q_0^{(1)}[/math], mentre [math]R[/math] porta a [math]q_0^{(0)}[/math]. La duplicazione dipende quindi dagli output degli archi entranti e non dal semplice numero di transizioni o di input possibili.

Domanda di riflessione: quale limite superiore si può usare per il numero di coppie stato-output nella conversione standard?

Risposte alle domande di riflessione

Quale proprietà formale distingue Moore da Mealy?

La differenza è nella funzione di output: in Moore vale [math]\lambda:Q\to\Delta[/math], quindi l’uscita dipende soltanto dallo stato; in Mealy vale [math]\lambda:Q\times\Sigma\to\Delta[/math], quindi l’uscita dipende dallo stato e dall’input corrente. La notazione dei diagrammi riflette questa scelta, collocando il valore dentro lo stato nel primo caso e sulla transizione nel secondo.

Dove si indica l’output di una macchina Mealy?

L’output è associato alla transizione e viene scritto dopo l’input, separato da una barra, come in [math]a/0[/math]. Per ogni simbolo letto, la macchina segue un arco e produce l’output specificato su quell’arco.

Che cosa cambia se il semaforo di Moore viene descritto con Mealy?

Nella rappresentazione Mealy gli output vengono assegnati alle transizioni e non direttamente agli stati. Di norma una sequenza di [math]n[/math] input produce [math]n[/math] output; se per la macchina Moore si include anche l’output dello stato iniziale, quella sequenza contiene invece [math]n+1[/math] valori. Per confrontare le rappresentazioni bisogna pertanto chiarire da quale istante si comincia a osservare l’uscita.

Perché Mealy può reagire entro il ciclo corrente?

In una realizzazione sincrona, la logica combinatoria di un’uscita Mealy può dipendere dall’ingresso corrente oltre che dallo stato registrato, così l’uscita può cambiare prima del successivo aggiornamento dello stato. Il momento effettivo dipende però dai ritardi di propagazione, dai campioni di input e dalla convenzione temporale adottata; parlare di un ritardo fisso di un ciclo senza descrivere l’architettura può essere fuorviante.

Quando Mealy e Moore possono avere lo stesso numero di stati?

I due modelli possono avere lo stesso numero di stati quando la funzione di output si rappresenta senza copie aggiuntive oppure quando la specifica associa naturalmente ciascun output a stati già presenti. La compattezza di Mealy è frequente in alcuni problemi, ma non è una proprietà universale che garantisca sempre un numero inferiore di stati.

Perché nella conversione Mealy → Moore si duplicano alcuni stati?

Una macchina Moore assegna un solo output a ogni stato. Se uno stato della macchina Mealy è raggiunto da transizioni con output diversi, una singola copia Moore non può rappresentare entrambi i valori; occorrono allora copie distinte, ciascuna associata a uno degli output entranti. Se tutti gli archi entranti producono lo stesso output, invece, una sola copia è sufficiente.

La conversione Mealy → Moore conserva sempre lo stesso numero di stati?

No. Il numero può aumentare per distinguere output diversi associati agli archi entranti in uno stesso stato. Nella costruzione standard, prima di eventuali ottimizzazioni, le coppie stato-output non superano [math]|Q|\times|\Delta|[/math]; questo è un limite superiore e non il numero previsto per ogni macchina. La convenzione sull’output iniziale può richiedere un trattamento ulteriore, che va dichiarato separatamente.

In quali situazioni Mealy può essere una rappresentazione naturale?

Mealy è adatto quando l’output rappresenta la risposta a un evento o dipende direttamente dall’input corrente, come accade in un rilevatore di sequenze, in un protocollo o in un traduttore. Può inoltre consentire una rappresentazione più compatta in alcune specifiche, purché il percorso input-output e la stabilità dei segnali siano compatibili con i requisiti del sistema.

Come cambia il modello se il verde pedonale dipende dal pulsante?

Se il verde pedonale deve dipendere direttamente dallo stato corrente e dal valore del pulsante, una funzione di output Mealy può rappresentare quel comportamento. In alternativa si può inserire uno stato Moore dedicato al verde pedonale; in tal caso l’uscita è associata allo stato raggiunto, e la macchina deve rispettare la temporizzazione richiesta dalla specifica.

Qual è il limite superiore nella conversione Mealy → Moore?

Nella costruzione standard, ciascuno stato originale può produrre al massimo una copia per ciascun output possibile, perciò il numero di coppie stato-output è al più [math]|Q|\times|\Delta|[/math]. In una macchina concreta molte di queste coppie non compaiono tra gli archi entranti e gli stati irraggiungibili possono essere rimossi, quindi il risultato è spesso più piccolo. Se il comportamento iniziale deve includere un output che Mealy non specifica, occorre descrivere la convenzione adottata prima di stabilire il conteggio complessivo.

Dalla macchina a stati al codice Python

Una FSM può essere controllata con un programma breve, purché la rappresentazione renda espliciti lo stato corrente e le transizioni ammesse. In una macchina Mealy il dizionario delle transizioni associa alla coppia stato-input lo stato successivo e l’output; in una macchina Moore associa la stessa coppia soltanto allo stato successivo, mentre un secondo dizionario assegna un output a ogni stato.

Le due funzioni seguenti simulano una sequenza di input senza dipendenze esterne. Se la macchina non definisce una transizione per una coppia stato-input, il simulatore segnala un errore: questo comportamento evita di inventare una risposta per combinazioni lasciate fuori specifica.

def simula_mealy(stato, sequenza_input, transizioni):
    output = []

    for simbolo in sequenza_input:
        try:
            stato, y = transizioni[(stato, simbolo)]
        except KeyError as errore:
            raise ValueError(
                f"Transizione Mealy non definita: stato={stato!r}, "
                f"input={simbolo!r}"
            ) from errore
        output.append(y)

    return stato, output


def simula_moore(
    stato,
    sequenza_input,
    transizioni,
    output_stato,
    includi_output_iniziale=False,
):
    output = [output_stato[stato]] if includi_output_iniziale else []

    for simbolo in sequenza_input:
        try:
            stato = transizioni[(stato, simbolo)]
        except KeyError as errore:
            raise ValueError(
                f"Transizione Moore non definita: stato={stato!r}, "
                f"input={simbolo!r}"
            ) from errore
        output.append(output_stato[stato])

    return stato, output

Per verificare il rilevatore sovrapposto di 101, definiamo prima le transizioni Mealy e Moore. Gli stati Mealy [math]S_0[/math], [math]S_1[/math] e [math]S_{10}[/math] ricordano il suffisso utile già letto; gli stati Moore [math]M_0[/math], [math]M_1[/math], [math]M_{10}[/math] e [math]M_{101}[/math] rappresentano gli stessi prefissi, con un’uscita 1 associata allo stato raggiunto dopo il completamento del pattern.

Per la macchina Moore il valore di ogni riga è l’output dello stato raggiunto dopo l’input; l’output iniziale [math]\lambda(M_0)=0[/math] viene mostrato separatamente, così non si confonde la sequenza successiva agli input con quella che include anche l’istante iniziale.

Nel flusso 10101 il pattern termina una prima volta al terzo bit e una seconda volta al quinto. Dopo il primo riconoscimento rimane utile il suffisso 1; per questo la macchina Mealy torna in [math]S_1[/math] e quella Moore, al bit successivo 0, passa da [math]M_{101}[/math] a [math]M_{10}[/math]. La sequenza di output dopo gli input è [math]0,0,1,0,1[/math] in entrambi i modelli; se in Moore si include anche l’output iniziale, la sequenza diventa [math]0,0,0,1,0,1[/math].

Il codice seguente contiene le due tabelle di transizione, esegue la simulazione e verifica con assert che entrambi i modelli segnalino il riconoscimento al terzo e al quinto input:

transizioni_mealy = {
    ("S0", "0"): ("S0", "0"),
    ("S0", "1"): ("S1", "0"),
    ("S1", "0"): ("S10", "0"),
    ("S1", "1"): ("S1", "0"),
    ("S10", "0"): ("S0", "0"),
    ("S10", "1"): ("S1", "1"),
}

transizioni_moore = {
    ("M0", "0"): "M0",
    ("M0", "1"): "M1",
    ("M1", "0"): "M10",
    ("M1", "1"): "M1",
    ("M10", "0"): "M0",
    ("M10", "1"): "M101",
    ("M101", "0"): "M10",
    ("M101", "1"): "M1",
}

output_moore = {
    "M0": "0",
    "M1": "0",
    "M10": "0",
    "M101": "1",
}

sequenza = "10101"
stato_mealy, uscite_mealy = simula_mealy(
    "S0", sequenza, transizioni_mealy
)
stato_moore, uscite_moore = simula_moore(
    "M0",
    sequenza,
    transizioni_moore,
    output_moore,
    includi_output_iniziale=False,
)

assert uscite_mealy == list("00101")
assert uscite_moore == uscite_mealy
assert stato_mealy == "S1"
assert stato_moore == "M101"

print("Output Mealy, dopo gli input:", uscite_mealy)
print("Output Moore, dopo gli input:", uscite_moore)
print("Output Moore, incluso lo stato iniziale:",
      simula_moore("M0", sequenza, transizioni_moore,
                   output_moore, includi_output_iniziale=True)[1])

Output Mealy, dopo gli input: ['0', '0', '1', '0', '1']
Output Moore, dopo gli input: ['0', '0', '1', '0', '1']
Output Moore, incluso lo stato iniziale: ['0', '0', '0', '1', '0', '1']

Una scelta legata al comportamento richiesto

Moore e Mealy non sono due notazioni intercambiabili in ogni dettaglio temporale. In Moore l’output descrive il valore associato allo stato attivo; in Mealy può descrivere anche la risposta all’input corrente. Da questa distinzione derivano il numero di stati richiesto in alcune costruzioni, il modo di leggere una sequenza di output e le scelte necessarie quando si converte una macchina.

La decisione dovrebbe partire dalla specifica: occorre stabilire se l’uscita rappresenta una condizione che permane finché resta attivo uno stato oppure una risposta che deve dipendere direttamente dall’evento ricevuto. Una volta chiarito questo punto, la funzione di output, la convenzione sul valore iniziale e i vincoli di temporizzazione rendono la scelta verificabile, anziché affidata a una regola generale.

Riferimenti per approfondire

• MathWorks, Overview of Mealy and Moore Machines, per le definizioni e la semantica dei due modelli nelle chart Stateflow.
• MathWorks, Convert Charts Between Mealy and Moore Semantics, con esempi di conversione e note sulla necessità di ridisegnare la macchina per preservare il comportamento.
• MathWorks, Sequence Recognition by Using Mealy and Moore Charts, con un esempio di riconoscimento di sequenza e confronto temporale.
• University of Washington, Introduction to Finite State Machines, materiale didattico introduttivo sui diagrammi e sulle definizioni.