Teoria da computação aula_5

Prévia do material em texto

Teoria da Computação
Prof. Ms. Diego Daniel 
Duarte
Faculdades Anhanguera
Limeira - SP
 
Cronograma
 
Tópicos
 Autômatos com Pilha
 
Autômato com Pilha
 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
– Pilha: memória adicional além da quantidade finita 
disponível na fita de entrada.
 Inicialmente a cabeça de leitura é posicionada na 
primeira célula, o controle finito do estado inicial e a 
Pilha está vazia.
 
Autômato com Pilha
a b b a b a Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura
$
Pilha
 
Autômato com Pilha
 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 e o símbolo no topo da pilha, é possível 
realizar uma operação. As operações podem ser:
1. Mover-se para um outro estado
2. Permanecer no mesmo estados
3. Mover-se para um outro estado e gravar um valor na pilha
4. Permanecer no mesmo estado e gravar um valor na pilha
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 com Pilha
 Função de Transição
– Constitui o “programa” do autômato com pilha
– Utilizada para descrever qual novo estado será assumido a 
partir de um dado estado ao se ler uma dada entrada e ao 
se ter um valor na pilha
– Mapeia elementos do conjunto de estados relacionados 
com o conjunto de entrada e o conjunto de valores da pilha 
em elementos do conjunto de estados relacionados com o 
conjunto de valores da pilha, ou seja:
 Estados x Entrada x Pilha  Estados x Pilha
 
Autômato com Pilha
a a c b b
Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura
$
Pilha
0
(a, $, B)
1
(a, ε, B)
(c, B, ε)
(b, B, ε)
2
(b, $, $)
 
Autômato com Pilha
a a c b b
Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura
$
B
Pilha
0
(a, $, B)
1
(a, ε, B)
(c, B, ε)
(b, B, ε)
2
(b, $, $)
 
Autômato com Pilha
a a c b b
Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura
$
B
B
Pilha
0
(a, $, B)
1
(a, ε, B)
(c, B, ε)
(b, B, ε)
2
(b, $, $)
 
Autômato com Pilha
a a c b b
Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura
$
B
Pilha
0
(a, $, B)
1
(a, ε, B)
(c, B, ε)
(b, B, ε)
2
(b, $, $)
 
Autômato com Pilha
a a c b b
Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura
$
Pilha
0
(a, $, B)
1
(a, ε, B)
(c, B, ε)
(b, B, ε)
2
(b, $, $)
 
Autômato com Pilha
a a c b b
Fita de Entrada
Unidade de Controle Finito
Estado 2
Cabeça Móvel de Leitura
$
Pilha
0
(a, $, B)
1
(a, ε, B)
(c, B, ε)
(b, B, ε)
2
(b, $, $)
 
Autômato com Pilha
 Um AFD é uma sextupla (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
� Γ é o alfabeto da pilha, ou seja, os símbolos que podem ser 
lidos e gravados da pilha
– s ∈ Q é o estado inicial do autômato
– F ⊆ Q é o conjunto de estados finais do autômato
� δ:QxΣεxΓε P(QxΓε) é a função de transição
 
Autômato com Pilha
 M = (Q, Σ, Γ, s, F, δ), no 
qual:
– Q = {0, 1, 2}
– Σ = {a, b, c}
� Γ = {B, $}
– s = 0
– F = { 2 }
� δ é dado por:
 δ(0, a, $) = (0, B)
 δ(0, a, ε) = (0, B)
 δ(0, c, B) = (1, ε)
 δ(1, b, B) = (1, ε)
 δ(1, b, $) = (2, $)
0
(a, $, B)
1
(a, ε, B)
(c, B, ε)
(b, B, ε)
2
(b, $, $)
 
Autômato com Pilha
 Aceitação de Entrada
– Uma data entrada para um autômato com pilha é 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 e 
a pilha encontra-se vazia
 Rejeição de Entrada
– Uma data entrada para um autômato com pilha é 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
 O autômato consegue ler toda a sequência da fita de entrada e, ao 
final da sua execução, a pilha não encontra-se vazia
 
Exercício
Seja M = (Q, Σ, Γ, s, F, δ), no qual:
– Q = {0, 1}
– Σ = {a, b}
� Γ = {B, $}
– s = 0
– F = { 1 }
� δ é dado por:
 δ(0, a, ε) = (0, B)
 δ(0, b, B) = (1, ε)
 δ(1, b, B) = (1, ε)
Diga se as entradas abaixo são aceitas 
ou rejeitadas pelo autômato:
1. aaabbb
2. aabbb
3. aaabb
	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