Máquina de moore2

Linguagens Formais e Autômatos Máquina de Moore, breve apresentação e definição e ompatação com Máquina de Mealey

1. Máquina de
Moore
Gleydson Silva
Graduando Ciência da computação
Ceut - centro de ensino unificado de teresina
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 1

2. Conteúdo abordado
Autômato finito com saída (Conceito chave)
Máquina de Mealy (Relembrar)
Máquina de Moore
Equivalência das máquinas de Moore e Mealy
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 2

3. Autômato finito com
saída
•O conceito básico de Autômato Finito, 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 entender a definição de Autômato Finito incluindo
a geração de uma palavra de saída.
•As saídas podem ser associadas as transições (Máquina
de Mealy) ou aos estados (Máquina de Moore)
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 3

4. Autômato finito com
saída
Em ambas as máquinas a saída não pode ser usada como
memória auxiliar e é da seguinte forma:
É definida sobre um alfabeto especial, denominado
Alfabeto de Saída (pode ser igual ao Alfabeto de entrada);
A saída é armazenada em uma fita independente da
entrada;
A cabeça da fita de saída, move uma célula para a direita a
cada símbolo gravado;
O resultado do processamento do Autômato Finito é o seu
estado final (condição aceita/rejeita ) e a informação
contida na fita de saída.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 4

5. Máquina de Mealy
(Relembrar)
A máquina de Mealy, é um autômato finito modificado de
forma a gerar uma palavra de saída para cada estado.
Uma Máquina de Mealy M, é um AFD, com saídas associadas
as transições. É representadas por uma 6-upla:
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 5

6. Máquina de Mealy
(Relembrar)
 Alfabeto de símbolos de entrada;
 Conjunto de estados possíveis do autômato, o qual é
finito;
 Função programa ou função de transição :
a qual é uma função parcial;
 Estado inicial do Autômato tal que q0, é elemento de
 Conjunto de estados finais, tal que é elemento de
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 6

7. Máquina de Mealy
(Relembrar)
 Alfabeto de símbolos de saída.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 7

8. Máquina de Mealy
(Relembrar)
O processamento de uma Máquina de Mealy, para uma
palavra de entrada w, consiste na sucessiva aplicação da
função programa para cada símbolo de w (da esquerda
para a direita) até ocorrer uma condição de parada.
A palavra vazia como saída da função programa indica que
nenhuma gravação é realizada e, obviamente, não move a
cabeça da fita de saída.
Se todas as transições geram saídas vazias, então a
Máquina de Mealy processa como se fosse um AF.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 8

9. Máquina de Moore
O que é ?
Como funciona?
Pra que serve?
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 9

10. Máquina de Moore
Definição:
Uma Máquina de Moore M, é um AFD, com saídas associadas
aos estados. É representado por uma 7-upla:
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 10

11. Máquina de Moore
 Alfabeto de símbolos de entrada;
 Conjunto de estados possíveis do autômato, o qual é
finito;
 Função programa ou função de transição :
a qual é uma função parcial;
 Estado inicial do Autômato tal que q0, é elemento de
 Conjunto de estados finais, tal que é elemento de
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 11

12. Máquina de Moore
 Alfabeto de símbolos de saída.
 Função de saída:
a qual é uma função total.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 12

13. Máquina de Moore
O processamento de uma Máquina de Moore, para uma
palavra de entrada w, consiste na sucessiva aplicação da
função de programa para cada símbolo de w ( da esquerda
para a direita ), até ocorrer uma condição de parada.
A palavra vazia resultado da função de saída, indica que
nenhuma gravação é realizada e , obviamente, não move a
cabeça da fita de saída.
Se todos os estados geram saída vazia, então a máquina
de Moore processa como se fosse um Autômato Finito.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 13

14. Máquina de Moore
Usabilidade:
Analisadores léxicos
Uma unidade léxica é associada a cada estado final;
Cada estado final possui uma saída (definida pela função de
saída ) que descreve ou codifica a unidade léxica identificada;
Para os demais estados ( não finais ) a saída gerada é uma
palavra vazia.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 14

15. Máquina de Moore
Exemplo:
Máquina de Moore que compacta brancos de um texto:
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 15

16. Máquina de Moore
MO=
tal que :
Demonstração para a entrada “aaaaββββββaaaaa”.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 16

17. Equivalência de
máquina de Moore e
Máquina de Mealy
Só será valida uma Equivalência de dois modelos de
autômatos finitos, para entradas não vazias;
Mostrar no quadro.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 17

18. Equivalência de
máquina de Moore e
Máquina de Mealy
Máquina de Moore → Máquina de Mealy
Toda Máquina de Moore, pode simular uma Máquina de
Mealy para entradas não vazias.
Suponha uma Máquina de Moore qualquer do tipo:
Seja uma Máquina de Mealy:
uma Máquina de Mealy, onde a função é definida
como segue (supunha “q” um estado de Q, e “a” um símbolo
de
.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 18

19. Equivalência de
máquina de Moore e
Máquina de Mealy
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 19

20. Equivalência de
máquina de Moore e
Máquina de Mealy
Em b, é construída a função programa da Máquina de
Mealy, a partir das funções de transição e de saídas da
Máquina de Moore.
O estado qe introduzido em a, é referenciado somente na
primeira transição a ser executada.
Seu objetivo é garantir a geração de saída referente ao
estado inicial q0 de Moore.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 20

21. Equivalência de
máquina de Moore e
Máquina de Mealy
Uma indução em n > 0, prova que ao reconhecer a entrada
a0,a1,...,an, Se MO passa pelos estados q0,q1,...,qn, e gera
as saídas u0,u1,...,un, então ME passa pelos estados
qe,q0,q1,..,qn e gera as saídas u0u1,...,um.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 21

22. Equivalência de
máquina de Moore e
Máquina de Mealy
Máquina de Mealy → Máquina de Moore
Toda Máquina de Mealy, pode simular uma Máquina de
Moore
Suponha uma Máquina de Mealy qualquer do tipo:
Seja: o conjunto de todas a saídas possíveis de ME
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 22

23. Equivalência de
máquina de Moore e
Máquina de Mealy
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 23

24. Equivalência de
máquina de Moore e
Máquina de Mealy
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 24

25. Equivalência de
máquina de Moore e
Máquina de Mealy
Prova-se por uma indução em n, que ao reconhecer a
entrada a1,a2,...,an, se ME passa pelos estados q0,q1,...,qn,
e gera as saídas u1,...,un, então MO passa pelos estados
<q0, e>,<q1, u1>, ... ,<qn, un> e gera as saídas ue,u1,...,un.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 25

26. Perguntas???
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 26

27. Referências:
Disponível em:< http://
pt.scribd.com/doc/61383869/1/Maquina-de-Mealy >Acesso
em: 12/11/2012
Disponível em:http://www.schulers.com/jpss/life/maq.htm
Acesso em: 12/11/2012
Disponível em:< http://
pt.scribd.com/doc/61383869/2/Maquina-de-Moore> Acesso
em: 12/11/2012
Disponível em:< http://
pt.scribd.com/doc/61383869/2/Maquina-de-Moore> Acesso
em: 12/11/2012
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 27

28. Referências:
Disponivel em:<http://
pt.scribd.com/doc/61383869/3/Equivalencia-das-Maquinas-de-Moore-e-de-Mealy
>Acesso em:12/11/2012
Menezes, P. Blauth. 1997. Linguagens Formais e Autômatos.
3ª edição. Porto Alegre: Editora Sagra Luzzato, 2000.
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 28

29. Contato:
Gleydson Cavalcante Silva
Graduando Ciência da Computação 5º Periodo
CEUT – Centro de Ensino Unificado de Teresina
Email: [email protected]
Facebook: fb.com/gleydsonbelfort
Gleydson Silva - Graduando Ciência da Computação: Linguagens Formais e Autômatos 29