Máquinas de Mealy e Moore

Prévia do material em texto

1 
 
Máquinas de Mealy e Moore 
Carlos Alberto do Nascimento 85489 
Lucas Ribeiro 87703 
Furg 
 
1 - Introdução 
As máquinas de estado finito são sistemas algébricos que podem ser divididos em duas 
categorias: as tradutoras ou Autômatos Finitos com Saída e as reconhecedores de linguagens, também 
conhecidas como Autômatos Finitos. 
O conceito básico de Autômatos Finitos possui aplicações restritas, pois a informação de saída 
é limitada à lógica binária aceita/rejeita. Sem alterar a classe de linguagens reconhecidas, é possível 
estender a definição de Autômato Finito incluindo a geração de uma palavra de saída. 
As máquinas de estado finito tradutoras possuem uma única entrada e uma única saída. Já as 
reconhecedoras de linguagens são máquinas onde, para cada entrada, existem duas saídas possíveis, 
uma para as sentenças válidas e outra para as sentenças inválidas da linguagem em questão, que 
devem ambas ser geradas a partir de gramáticas regulares. Todas têm memória finita e baseada no 
conceito de "estados". 
As máquinas de estado podem ser classificadas em Máquina de Moore, onde a saída 
depende apenas do seu estado atual e Máquina de Mealy, que possui uma saída que depende 
de seu estado atual e de sua entrada atual. 
 
2 - Definições Formais 
Uma Máquina de Mealy M é autômato finito determinístico com saídas associadas às 
transições. É representada pela 6-upla M = (Σ, Q, δ, q0, F, ∆). 
Onde: 
• Σ é um alfabeto de símbolos de entrada. 
• Q é um conjunto de estados possíveis do autômato, o qual é finito. 
• δ é a função programa ou de transição δ: Q x Σ -> Q x ∆*. 
• q0 é o estado inicial do autômato, tal que q0 é elemento de Q. 
• F é um conjunto de estados finais tal que F está contido em Q. 
• ∆ é um alfabeto de símbolos de saída. 
O processamento de uma Máquina de Mealy para uma dada entrada w consiste na aplicação 
sucessiva da função programa para cada símbolo de w (da esquerda para a direita), até ocorrer uma 
condição de parada. Caso a saída da função programa seja uma palavra vazia, nenhuma gravação é 
realizada, ou seja, a cabeça da fita não se move. Porém se todas as transições de uma determinada 
máquina de Mealy gerarem saídas vazias, então esta se comporta como um Autômato Finito. 
 
 
 2 
 
Já uma Máquina de Moore M, como dito anteriormente, é um Autômato Finito Determinístico 
com suas saídas associadas aos estados. É representada pela 7-upla M = (Σ, Q, δ, q0, F, ∆, δS). 
Onde: 
• Σ é um alfabeto de símbolos de entrada. 
• Q é um conjunto de estados possíveis do autômato, o qual é finito. 
• δ é a função programa ou de transição δ: Q x Σ -> Q.. 
• q0 é o estado inicial do autômato, tal que q0 é elemento de Q. 
• F é um conjunto de estados finais tal que F está contido em Q. 
• ∆ é um alfabeto de símbolos de saída. 
• δS é a função de saída δS: Q -> ∆* a qual é uma função total. 
O processamento de uma Máquina de Moore ocorre da mesma forma que na máquina de Mealy, 
assim como o tratamento de saídas vazias. Assim como a Máquina de Mealy, se todos os seus estados 
gerarem saída vazia, ela também se comporta como um Autômato Finito. 
 
3 - Exemplos 
 
Máquina de Mealy que produz NOT. 
 
 
Máquina de Moore que produz NOT. 
 
 
4 - Aplicação 
Máquina de Mealy: 
Abaixo temos um exemplo de uma máquina de venda automática que libera o doce uma vez que 
o dinheiro suficiente foi inserido e retorna a quantidade certa de troco. 
 
 
 3 
 
 
V = ({0c, 5c, 10c, 15c}, {n, d, q}, {c0, c1, c2, c3, c4}, δ, ω, 0c} 
 
Esta máquina de Mealy tem quatro estados, 0c, 5c, 10c e 15c, cada um descrevendo a 
quantidade de dinheiro inserida na máquina de venda automática. Seu alfabeto de entrada de n, d, e q, 
denota a inserção de 5 centavos, 10 centavos e 25 centavos. Em seu alfabeto de saída, λ denota a 
máquina de venda automática não fazendo nada, enquanto c0, c1, c2, c3 e c4 denotam a liberação do 
doce ou não, e os trocos 1, 5, 10 e 25, respectivamente. 
Máquina de Moore: 
Abaixo temos um exemplo de uma máquina Moore que reduz para metade os números binários. 
 
Há quatro permutações possíveis de dois bits consecutivos, 00, 01, 10 e 11, e cada um é 
representado por um estado na máquina. Por exemplo, o estado 01 significa que o bit de entrada mais 
recente era 1 e o bit de entrada anterior a 0. Cada estado produz a saída equivalente ao segundo bit 
de entrada mais recente e armazena o bit mais recente para retransmitir essa informação Para o 
próximo estado (onde se tornará o segundo bit de entrada mais recente). 
 
 
 
 
 4 
 
5 - Equivalência entre as Máquinas 
A equivalência dos dois modelos de Autômato Finito com Saída não é válida para a entrada 
vazia. Neste caso, enquanto a Máquina de Moore gera a palavra correspondente ao estado inicial, a 
Máquina de Mealy não gera qualquer saída, pois não executa transição alguma. Entretanto, para os 
demais casos, a equivalência pode ser facilmente mostrada. 
Assim, toda Máquina de Moore pode ser simulada por uma Máquina de Mealy, para entradas 
não vazias, e Toda Máquina de Mealy pode ser simulada por uma Máquina de Moore. No caso de 
saídas vazias, o que ocorre é que enquanto a Máquina de Moore gera a palavra correspondente ao 
estado inicial, a Máquina de Mealy não gera qualquer saída, pois não executa transição alguma, 
tornando assim as duas incompatíveis. 
 
6 - Conclusões 
Foi exemplificado o funcionamento das máquinas de Moore e Mealy, esclarecendo as 
semelhanças e as diferenças entre as mesmas e evidenciando seu processo de análise. A 
equivalência dos dois modelos de Autômato Finito com Saída abordadas nas Máquinas de Estados 
Finitos não é válida para a entrada vazia. Enquanto a Máquina de Moore gera a palavra 
correspondente ao estado inicial, a Máquina de Mealy não gera qualquer saída, pois não executa 
transição alguma. Entretanto, para os demais casos, a equivalência pode ser facilmente mostrada. 
 
7 - Referências 
 
CDT314 Formal Languages, Automata and Theory of Computation, Mälardalen University – School of 
Innovation, Design and Engineering, 24 11 2011. 
Roberta C. de Brito, Diogo M. Martendal, Henrique Eduardo M. de Oliveira - Máquinas de estados 
finitos de Mealy e Moore. Universidade Federal de Santa Catarina (UFSC), 2003. 
Paulo Blauth Menezes - Linguagens Formais e Autômatos. 3ª Ed. 
JFLAP Tutorial – Examples of Mealy Machine, Moore Machine. 
Caroline Obregon Pilz - Máquinas de Mealy e Moore. UFSM, 2015. 
 
 
 
 
 
 
 
 
 
 5 
 
 
Questão 2 – Atividade Complementar 1 
O Autômato finito apresentado na resposta é caracterizado como determinístico pois cada 
movimento é determinado de uma única forma, como no exercícios a linguagem é de apenas dois 
caracteres, todos os estados possuem dois "caminhos". Logo, concluímos que a linguagem é regular 
pois, a partir dela é possível se construir um AFD. 
 
 
Imagem questão 2 
 
 
 
 
 
 
 
 
 6 
 
 
Questão 3 – Atividade Complementar 1 
Assim como no exercício 2, o autômato apresentado é Determinístico pois apresenta apenas 
dois "caminhos" para cada estado, e reconhece todas as cadeias originarias da linguagem 
apresentada, por consequência, a linguagem também é regular. 
 
 
Imagem questão 3