Differenza tra Mealy e Moore

Question

La differenza tra le macchine di stato Mealy e Moore ha un reale significato quando si tratta di un'implementazione C? Quale sarebbe normalmente questa differenza?

Molto tempo fa, per me è stato molto più facile capire i vantaggi/svantaggi di Mealy/Moore quando si tratta di RTL. L'intera uscita a seconda dello stato/uscita corrente a seconda dello stato corrente + differenza di input corrente aveva senso, così come il fatto che Mealy potesse essere realizzato con uno stato in meno in alcuni casi aveva anche senso. L'associazione dei diagrammi temporali a ciascuna implementazione di FSM ha inoltre reso più chiara la differenza tra loro.

Dire che sto facendo una macchina a stati in C. In un caso un LUT dipende dagli ingressi stato/corrente (Mealy) e nel Moore il LUT guarda solo sullo stato corrente e restituisce il successivo. In entrambi l'output avviene dopo il ritorno dalla LUT (penso, anche se potrei sbagliarmi). Non ho pensato a un modo chiaro che un Mealy abbia un vantaggio quando è codificato in C. Argomenti come la leggibilità del codice, la velocità, la densità del codice, la facilità di progettazione, possono essere tutti argomenti rilevanti - dal mio punto di vista i due modelli sembrano quasi la stessa cosa.

Forse questa differenza è solo un argomento per gli accademici - e in pratica nelle implementazioni C la differenza è trascurabile. Se si conoscono i modi principali in cui un'implementazione della macchina a stati C differirebbe tra Mealy e Moore, e se ci sono reali vantaggi (che sono anche significativi) sarei curioso di sapere. Vorrei sottolineare - Non sto chiedendo di implementazioni RTL.

ho visto un altro post Mealy/Moore qui: Mealy v/s. Moore

Ma questo non è davvero il livello di spiegazione che sto cercando.

Answer 1

Hai una procedura meccanica per convertire un formalismo nell'altro, quindi non c'è alcuna differenza strutturale tra i due.

Per quanto riguarda le differenze di implementazione, i due formalismi differiscono solo nella funzione di uscita , che indica quale simbolo deve essere emesso. In particolare:

1. In una macchina di Moore, l'uscita dipende solo dallo stato attuale
2. In una macchina farinoso, l'uscita dipende dallo stato attuale e l'ingresso corrente.

una macchina Moore potrebbe essere un po 'più semplice da implementare perché hai meno informazioni da tracciare quando si tratta di generare l'output, ma la differenza sarà veramente piccola.

Ecco come una semplice macchina di Moore sarebbe simile a C:

int state = INITIAL; 
while (!isTerminal(state)) { 
    char input = nextInputSymbol(); 
    fprintf(output, "%c", nextOutputSymbol(state)); 
    state = nextState(state, input); 
} 

e qui è la macchina Mealy:

int state = INITIAL; 
while (!isTerminal(state)) { 
    char input = nextInputSymbol(); 
    fprintf(output, "%c", nextOutputSymbol(input, state)); 
    state = nextState(state, input); 
} 

, come si vede, l'unica differenza è nella definizione di nextOutputSymbol(). Se l'implementazione di detta funzione è più facile per l'uno o l'altro formalismo, dipende davvero dall'applicazione specifica.

nextInputSymbol è solo una routine per ottenere un nuovo simbolo (potrebbe essere un scanf o simili) e nextState dipenderà dalla specifica macchina, ma la sua complessità non cambierà molto tra Mealy ed equivalente Moore.

In particolare, sia nextOutputSymbol e nextState riducono ad una tabella di ricerca o un switch o una catena if/else, senza alcuna difficoltà reale attuazione. Sono semplicemente noiosi da scrivere, davvero.

NOTA: Ho omesso il controllo degli errori nei frammenti di codice per tenerci concentrati sul punto principale della discussione. Il codice reale eseguirà alcuni controlli extra, come la gestione di EOF su nextInputSymbol o break sugli stati di errore.

Answer 2

Moore Machine: la stampa dipende solo dallo stato attuale. Mealy Machine: la produzione dipende dallo stato attuale & presente.