Macchina di Mealy
Nella teoria della calcolabilità, la macchina di Mealy è un automa a stati finiti che genera un'uscita a partire dagli stati d'ingresso e dallo stato corrente, a differenza della macchina di Moore, che invece lavora solo in funzione dello stato corrente. Tuttavia, per ogni macchina di Mealy esiste una macchina di Moore equivalente.
L'automa 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 l'alfabeto degli ingressi e delle uscite le lettere dell'alfabeto latino, l'automa 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.
[modifica] Definizione formale
Una macchina di Mealy è 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)
- una funzione uscita (G : S × Σ → Λ)
