Indietro

ⓘ Macchina di Mealy




Macchina di Mealy
                                     

ⓘ Macchina di Mealy

Nella teoria della calcolabilità, la macchina di Mealy è un automa a stati finiti i cui valori di uscita sono determinati dallo stato attuale e dallingresso corrente, a differenza della macchina di Moore, che invece lavora solo in funzione dello stato corrente. Tuttavia, non per tutte le macchine di Mealy si può definire una macchina di Moore equivalente. In quanto il modello di Mealy basa lo stato duscita della macchina sia sullo stato in cui si trova, sia sugli input che riceve la macchina, mentre il modello di Moore è valido per le macchine che basano loutput soltanto sullo stato corrente della macchina, indifferentemente dagli input.

Lautoma deve il suo nome al suo promotore, lo statunitense G. H. Mealy, che lo descrisse nel trattato A Method for Synthesizing Sequential Circuits nel 1955.

La macchina di Mealy fornisce un rudimentale modello matematico per le macchine cifrate. Utilizzando per lalfabeto degli ingressi e delle uscite le lettere dellalfabeto latino, lautoma può lavorare su una data stringa di lettere ovvero una sequenza di ingressi che provvede a convertire in una stringa cifrata ossia una sequenza di uscite. Sebbene sia possibile, ad esempio, descrivere Enigma attraverso una macchina di Mealy, il diagramma degli stati risulterebbe troppo complicato per capire il funzionamento delle macchine cifrate.

                                     

1. Definizione formale

Una macchina di Mealy è una sestupla, { S, S 0, Σ, Λ, T, G }, costituita da:

  • una funzione di transizione T: S × Σ → S
  • un insieme finito chiamato alfabeto delle uscite Λ
  • un insieme finito di stati S
  • un insieme finito chiamato alfabeto degli ingressi Σ
  • una funzione uscita G: S × Σ → Λ
  • uno stato iniziale S 0, che è un elemento di S