Máquina de moore2

gleydsonjiujitsu 1,108 views 29 slides Apr 13, 2013
Slide 1
Slide 1 of 29
Slide 1
1
Slide 2
2
Slide 3
3
Slide 4
4
Slide 5
5
Slide 6
6
Slide 7
7
Slide 8
8
Slide 9
9
Slide 10
10
Slide 11
11
Slide 12
12
Slide 13
13
Slide 14
14
Slide 15
15
Slide 16
16
Slide 17
17
Slide 18
18
Slide 19
19
Slide 20
20
Slide 21
21
Slide 22
22
Slide 23
23
Slide 24
24
Slide 25
25
Slide 26
26
Slide 27
27
Slide 28
28
Slide 29
29

About This Presentation

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


Slide Content

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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