Teoria da computação aula_4

Prévia do material em texto

Teoria da Computação
Prof. Ms. Diego Daniel 
Duarte
Faculdades Anhanguera
Limeira - SP
 
Cronograma
 
Tópicos
 Representação da Computação (pag. 32 
[SIPSER])
 Autômatos Finitos Determinísticos (pag. 66)
 Autômatos Finitos Indeterminísticos (pag. 73)
 
Representação da Computação
 Como visto anteriormente, a computação é 
dada pela sequência:
– Informação na Memória
– Instrução a ser executada
 Ambos elementos juntos compõe o estado 
da máquina
 O estado da máquina é alterado de acordo 
com a entrada recebida
 
Representação da Computação
 Dado um estado qualquer 
da máquina, para uma dada 
entrada, a máquina pode:
– Manter o mesmo estado
– Alterar seu estado
– Não ter operação para 
realizar
 Podemos representar essas 
possibilidades com o auxílio 
de um grafo
 
Autômato Finito
 Mecanismos:
– Fita de Entrada: composta por células, com símbolos 
gravados em cada célula.
– Cabeça Móvel de Leitura: lê uma célula da fita e desloca-
se para a direita
– Controle Finito: bloco composto pelos diferentes estados 
que o autômato pode assumir
 Inicialmente a cabeça de leitura é posicionada na 
primeira célula, e o controle finito do estado inicial
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura
 
Autômato Finito
 Funcionamento
1. A cabeça móvel de leitura lê o símbolo na célula atual da 
fita e movimenta-se para a direita
2. A unidade de controle finito identifica se, à partir do 
estado atual, com a entrada lida, é possível realizar uma 
operação. As operações podem ser:
1. Mover-se para um outro estado
2. Permanecer no mesmo estados
3. Se nenhuma operação for possível de ser realizada, o 
autômato para
4. Se o final da Fita de entrada for atingido, a máquina para
 
Autômato Finito
 Função de Transição
– Constitui o “programa” do autômato finito
– Utilizada para descrever qual novo estado será 
assumido a partir de um dado estado ao se ler 
uma dada entrada
– Mapeia elementos do conjunto de estados 
relacionados com o conjunto de entrada em 
elementos do conjunto de estados, ou seja, 
Estados x Entrada  Estados
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura
0
1
a
b b
a
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura
0
1
a
b b
a
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura
0
1
a
b b
a
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura
0
1
a
b b
a
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura
0
1
a
b b
a
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura
0
1
a
b b
a
 
Autômato Finito
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura
0
1
a
b b
a
 
Autômato Finito Determinístico
 Um AFD é uma quíntupla (Q, Σ, s, F, δ), no qual:
– Q é o conjunto de estados que o autômato pode assumir
– Σ é o alfabeto reconhecido pelo autômato, ou seja, os 
símbolos que podem aparecer na fita de entrada
– s ∈ Q é o estado inicial do autômato
– F ⊆ Q é o conjunto de estados finais do autômato
� δ:QxΣQ é a função de transição
 
Autômato Finito Determinístico
 M = (Q, Σ, s, F, δ), no 
qual:
– Q = {0, 1}
– Σ = {a, b}
– s = 0
– F = { 0 }
� δ é dado por:
 δ(0, a) = 0
 δ(0, b) = 1
 δ(1, a) = 1
 δ(1, b) = 0
0
1
a
b b
a
 
Autômato Finito Determinístico
 Aceitação de Entrada
– Uma data entrada para um autômato finito determinístico é 
dita aceita se o autômato consegue ler toda a sequência 
da fita de entrada e, ao final de sua execução, ele 
encontra-se em um dos estados finais
 Rejeição de Entrada
– Uma data entrada para um autômato finito determinístico é 
dita rejeitada se ou:
 O autômato não consegue ler toda a sequência da fita de 
entrada;
 O autômato consegue ler toda a sequência da fita de entrada 
e, ao final da sua execução, ele não encontra-se em nenhum 
dos estados finais
 
Exercício
Seja M = (Q, Σ, s, F, δ), no qual:
– Q = {0, 1, 2}
– Σ = {a, b}
– s = 0
– F = { 0, 1 }
� δ é dado por:
 δ(0, a) = 0
 δ(0, b) = 1
 δ(1, a) = 0
 δ(1, b) = 2
 δ(2, a) = 2
 δ(2, b) = 2
Diga se as entradas abaixo são aceitas 
ou rejeitadas pelo autômato:
1. abbaba
2. abaabab
 
Autômato Finito Indeterminístico
 Um AFN é uma quíntupla (Q, Σ, s, F, ∆), no qual:
– Q é o conjunto de estados que o autômato pode assumir
– Σ é o alfabeto reconhecido pelo autômato, ou seja, os 
símbolos que podem aparecer na fita de entrada
– s ∈ Q é o estado inicial do autômato
– F ⊆ Q é o conjunto de estados finais do autômato
� ∆:QxΣQ* é a função de transição
 Basicamente, um AFN é um AFD no qual, para um 
dado estado, podem existir mais de uma saída para 
o mesmo símbolo lido da fita.
 
Autômato Finito Indeterminístico
 M = (Q, Σ, s, F, δ), no 
qual:
– Q = {0, 1}
– Σ = {a, b}
– s = 0
– F = { 0 }
� ∆ é dado por:
 ∆(0, a) = { 0 }
 ∆(0, b) = { 0, 1 }
 ∆(1, a) = { 1 }
 ∆(1, b) = { 0 }
0
1
a,b
b b
a
 
Autômato Finito Indeterminístico
 Aceitação de Entrada
– Uma data entrada para um autômato finito determinístico é dita 
aceita se o autômato consegue ler toda a sequência da fita de 
entrada e existe ao menos uma execução que, ao finalizada, 
permita que o autômato encontre-se em um dos estados finais
 Rejeição de Entrada
– Uma data entrada para um autômato finito determinístico é dita 
rejeitada se ou:
 O autômato não consegue ler toda a sequência da fita de entrada;
 O autômato consegue ler toda a sequência da fita de entrada mas 
não existe nenhuma execução que, ao finalizada, permita que o 
autômato encontre-se em um dos estados finais
 
Exercício
Seja M = (Q, Σ, s, F, ∆), no qual:
– Q = {0, 1, 2}
– Σ = {a, b}
– s = 0
– F = { 0, 1 }
� ∆ é dado por:
 ∆(0, a) = { 0, 1, 2 }
 ∆(0, b) = { 1, 2 }
 ∆(1, a) = { 0 }
 ∆(1, b) = { 2 }
 ∆(2, a) = { 1, 2 }
 ∆(2, b) = { 2 }
Diga se as entradas abaixo são aceitas 
ou rejeitadas pelo autômato:
1. abbaba
2. abaabab
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24