Macchina di Moore
Da Wikipedia, l'enciclopedia libera.
Nella teoria della calcolabilità, la macchina di Moore è un automa a stati finiti in cui le uscite sono determinate in funzione dei soli stati correnti (e non anche dagli stati d'ingresso, come accade invece nella macchina di Mealy). Il Diagramma di stato di una macchina di Moore prevede un segnale d'uscita per ciascuno stato. L'automa deve il suo nome al suo promotore, lo statunitense Edward F. Moore, professore di matematica ed informatica all'università del Wisconsin-Madison, che lo descrisse nel trattato Gedanken-experiments on Sequential Machines.
La maggior parte dei sistemi elettronici digitali vengono progettati come sistemi sequenziali ad impulsi di clock, che sono una forma ridotta della macchina di Moore, dove lo stato cambia solo quando varia il segnale globale di clock. Generalmente lo stato corrente viene salvato nei flip-flop, mente il segnale globale di clock viene collegato nell'ingresso dei flip-flop riservato al clock. I sistemi sequenziali ad impulsi di clock sono solo un modo di risoluzione dei problemi di metastabilità. Una tipica macchina di Moore elettronica comprende una sequenza logica combinatoria per decodificare lo stato corrente nelle uscite (lambda). Nel momento in cui lo stato corrente viene modificato, il cambio si ripercuote sull'intera sequenza, modificando (o meno) quasi istantaneamente anche le uscite. Esistono diverse tecniche di progettazione che tendono a limitare eventuali bug durante il breve periodo di modifica, ma la maggior pare dei sistemi sono costruiti in maniera tale che questi "buchi" vengano ignorati o considerati irrilevanti. Le uscite conservano indefinitamente il loro stato, fintanto che la macchina non cambi nuovamente stato.
[modifica] Definizione formale
Una macchina di Moore può essere definita come una sestupla { S, S0, Σ, Λ, T, G } costituita da:
- un insieme finito di stati (S)
- uno stato iniziale S0, che è un elemento di (S)
- un insieme finito chiamato alfabeto degli ingressi ( Σ )
- un insieme finito chiamato alfabeto delle uscite ( Λ )
- una funzione di transizione (T : S × Σ → S) che mappa uno stato ed un ingresso allo stato prossimo
- una funzione uscita (G : S → Λ) che mappa ciascun stato nell'alfabeto delle uscite
Il numero di stati in una macchina di Moore machine sarà maggiore o uguale al numero di stati della corrispondente macchina di Mealy.
