Máquina de Mealy
A Máquina de Mealy é um Autômato Finito modificado de tal forma que gere uma palavra de saída para cada transição, baseando-se no estado em que se encontra e na entrada de dados. Assim o diagrama de estados irá incluir tanto o sinal de entrada como o de saída para cada vértice de transição.
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”, em setembro de 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 seqüência de entrada de dados), ela pode processá-la numa série cifrada (uma seqüê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.
Definição Formal
Conforme [Machado] uma Máquina de Mealy é um Autômato Finito modificado de forma a gerar uma palavra de saída para cada transição. É uma 6-tupla, M = (Q, Σ, Δ ,δ, q0, F). A função de transição pode ser representada por um Grafo Finito Direto, assim como nos autômatos finitos, adicionando a cada etiqueta de transição, a saída associada, quando diferente da palavra vazia.
O processamento para uma palavra de entrada w, consiste na sucessiva aplicação da função de transição para cada símbolo de w (da esquerda para a direita) até que ocorre alguma condição de parada. A palavra vazia como saída da função programa indica que nenhuma gravação é realizada, não movendo a cabeça da fita de saída. Se todas as transições geram saída vazia, então a Máquina de Mealy processa como se fosse um Autômato Finito.
Como uma Máquina de Mealy tem uma entrada para uma única saída, não pode existir não-determinismo. Embora que ainda sejamos capazes de construir uma Máquina de Mealy que tenha não-determinismo, nós não seremos capazes de executar uma entrada nela.
Exemplo de uma Máquina de Mealy
Uma aplicação comum e freqüentemente recomendada para os autômatos com saída é o projeto de diálogo entre um programa de computador e o seu usuário. O diálogo pode ser comandado pelo programa ou pelo usuário. Uma das dificuldades do projetista é a visualização do conjunto de eventos e ações que definam um diálogo adequado para as diversas situações possíveis.
Equivalência entre Máquinas de Moore e de Mealy
As Máquinas de Moore e de Mealy são Autômatos Finitos com Saída. Elas são equivalentes para entradas não vazias. Com uma entrada vazia a Máquina de Mealy não gera saída pois não executa nenhuma transição (a saída está associada à transição), enquanto que a Máquina de Moore gera a palavra correspondente ao estado inicial (a saída está associada ao estado). Segundo [Menezes] uma Máquina de Mealy possui, em geral, menos estados que a correspondente
Máquina de Moore.
Posts relacionados:
- Características Essenciais no Projeto de Linguagens de Programação
- O que são compiladores?
- Salvar um arquivo de texto em Java
- Perguntas Interessantes
- Teoria dos jogos
Tags: teoria da computacao