Teoria da computação aula_6

Prévia do material em texto

Teoria da Computação
Prof. Ms. Diego Daniel 
Duarte
Faculdades Anhanguera
Limeira - SP
 
Cronograma
 
Tópicos
 Máquina de Turing
 
Máquina de Turing
 Mecanismos:
– Fita de Entrada: memória infinita composta por células, com 
símbolos gravados em cada célula à esquerda e em braco para o 
restante da fita.
– Cabeça Móvel de Leitura e Gravação: lê ou grava em uma 
célula da fita e desloca-se para a direita ou para a esquerda
– Controle Finito: bloco composto pelos diferentes estados que a 
máquina pode assumir pode assumir
 Inicialmente a fita é preenchida com a entrada nas células 
mais à esquerda, ficando as células mais à direita em branco, 
cabeça de leitura e gravação é posicionada na primeira célula 
à esquerda, o controle finito do estado inicial.
 
Máquina de Turing
a b b a b ...
Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura e 
Gravação
 
Máquina de Turing
 Diferença MT x AF
– Uma Máquina de Turing pode tanto escrever 
sobre a fita quanto ler à partir dela
– A cabeça de leitura e gravação pode mover-se 
tanto para a esquerda quanto para a direita
– A fita de entrada é infinita
– A máquina contém estados especiais para 
aceitar e rejeitar a entrada que entram em efeito 
imediatamente
 
Máquina de Turing
 Um MT é uma setupla (Q, Σ, Γ, s, b, F, δ), no qual:
– Q é o conjunto de estados que o autômato pode assumir
– Σ é o alfabeto de entrada sem o símbolo de branco
� Γ é o alfabeto da fita
– s ∈ Q é o estado inicial do autômato
– b é o símbolo de branco da fita
– F ⊆ Q é o conjunto de estados finais
� δ:QxΓ QxΓx{E, D} é a função de transição
 
Máquina de Turing
 M = (Q, Σ, Γ, s, b, F, δ), no 
qual:
– Q = {0, 1, 2}
– Σ = {a, b}
� Γ = {a, b, A, B, $}
– s = 0
– B = $
– F = { 2 }
� δ é dado por:
 δ(0, a) = (1, A, D)
 δ(0, b) = (0, B, D)
 δ(0, $) = (2, $, D)
 δ(1, a) = (0, A, D)
 δ(1, b) = (1, B, D)
1
(b, B, D)
0
(a, A, D)
(b, B, D)
2
($, $, D)
(a, A, D)
 
Máquina de Turing
a b b a b
Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura e 
gravação
1
(b, B, D)
0
(a, A, D)
(b, B, D)
2
($, $, D)
(a, A, D)
$
 
Máquina de Turing
A b b a b
Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura e 
gravação
1
(b, B, D)
0
(a, A, D)
(b, B, D)
2
($, $, D)
(a, A, D)
$
 
Máquina de Turing
A B b a b
Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura e 
gravação
1
(b, B, D)
0
(a, A, D)
(b, B, D)
2
($, $, D)
(a, A, D)
$
 
Máquina de Turing
A B B a b
Fita de Entrada
Unidade de Controle Finito
Estado 1
Cabeça Móvel de Leitura e 
gravação
1
(b, B, D)
0
(a, A, D)
(b, B, D)
2
($, $, D)
(a, A, D)
$
 
Máquina de Turing
A B B A b
Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura e 
gravação
1
(b, B, D)
0
(a, A, D)
(b, B, D)
2
($, $, D)
(a, A, D)
$
 
Máquina de Turing
A B B A B
Fita de Entrada
Unidade de Controle Finito
Estado 0
Cabeça Móvel de Leitura e 
gravação
1
(b, B, D)
0
(a, A, D)
(b, B, D)
2
($, $, D)
(a, A, D)
$
 
Máquina de Turing
 Aceitação de Entrada
– Uma data entrada para uma máquina de turing é dita aceita se a 
máquina consegue chegar a um dos estados finais
 Rejeição de Entrada
– Uma data entrada para uma máquina de turing é dita rejeitada se 
a máquina não consegue chegar a um dos estados finais
 Looping
– Eventualmente uma Máquina de Turing pode permanecer em um 
processamento constante, tendo sempre uma operação a ser 
realizada, mas nunca atingindo um estado final. Nesses casos diz-
se que a máquina está em um looping infinito
 
Exercício
Seja M = (Q, Σ, Γ, s, b, F, δ), no qual:
– Q = {0, 1, 2, 3, 4}
– Σ = {a, b}
� Γ = {a, b, x, $}
– s = 0
– b = $
– F = { 4 }
� δ é dado por:
 δ(0, a) = (1, x, D)
 δ(0, b) = (2, x, D)
 δ(0, $) = (4, $, E)
 δ(0, x) = (0, x, D)
 δ(1, a) = (1, a, D)
 δ(1, b) = (0, x, E)
 δ(2, a) = (0, x, E)
 δ(2, b) = (2, b, E)
Diga se as entradas abaixo são aceitas ou 
rejeitadas pelo autômato:
1. aaabbb
2. aabbb
3. aaabb
4. abaabb
	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