Máquina de Mealy
Em ciências da computação, uma máquina de Mealy é uma máquina de estado finito que produz um resultado (saída de dados) baseando-se no estado em que se encontra e na entrada de dados. Isto significa que o diagrama de estados irá incluir tanto o sinal de entrada como o de saída para cada vértice de transição. Em contraste, a saída de uma máquina de Moore depende apenas do estado actual da máquina, sendo que as transições não possuem qualquer sinal em anexo. Mesmo assim, por cada máquina de Mealy existe uma máquina de Moore equivalente cujos estados consistem na união dos estados da máquina de Mealy e o produto cartesiano dos estados da máquina de Mealy com o alfabeto de entrada de sinais.
O nome "máquina de Mealy" tem origem no nome do promotor do conceito: G. H. Mealy, um pioneiro das máquinas de estado, que escreveu A Method for Synthesizing Sequential Circuits, Bell System Tech. J. vol 34, pp. 1045–1079, September 1955.
As máquinas de Mealy oferecem um modelo matemático rudimentar para definir máquinas de cifras. Considerando como alfabeto de entrada e de saída o alfabeto latino, por exemplo, então a máquina de Mealy pode ser desenhada de forma a que dada uma série de letras (uma sequência de entrada de dados), ela pode processá-la numa série cifrada (uma sequência de saída de dados). No entanto, apesar de ser possível descrever a Enigma através duma máquina de Mealy, o diagrama de estados seria demasiado complexo para se considerar um método cómodo para desenhar máquinas de cifra.
Dada uma máquina de Mealy equivalente a uma máquina de Moore, podemos afirmar que o número de estados que a descreve pode ser simplificado até um número de estados menor ou igual a qualquer máquina de Moore equivalente. Ou seja: máquinas de Mealey, na prática, são de implementação mais econômica. Em contrapartida, podemos afirmar que máquinas de Moore podem ser munidas de maior estabilidade.
Definição formal editar
Uma máquina de Mealy é um 6-tuplo (S, S0, Σ, Λ, T, G), que consistem em
- um conjunto finito de estados (S)
- um estado inicial S0 que é um elemento de S
- um conjunto finito chamado o alfabeto de entrada (Σ),
- um conjunto finito chamado o alfabeto de saída (Λ)
- uma função de transição (T : S × Σ → S)
- uma função de saída de dados (G : S × Σ → Λ)