Linguagens Formais e Aut matos Aula 9 M quina de Turing 23.05.2017.2

Prévia do material em texto

Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Máquina de Turing
• A máquina de Turing é um dispositivo teórico
conhecido como máquina universal, que foi
concebido pelo matemático britânico Alan Turing
(1912-1954), muitos anos antes de existirem os
modernos computadores digitais (em 1936).
• Num sentido preciso, é um modelo abstrato de um
computador, que se restringe apenas aos aspectos
lógicos do seu funcionamento (memória, estados e
transições) e não à sua implementação física.
• A Máquina de Turing é um formalismo muito
simples, universalmente conhecido e
provavelmente o mais usado como modelo teórico
da computação.
• Por definição, se uma linguagem é reconhecida por
alguma máquina de Turing, ela é recursivamente
enumerável ou do Tipo 0.
• Em Matemática, Lógica e Ciência da Computação,
uma linguagem recursivamente enumerável é um
tipo de Linguagem formal (Tipo 0) que também é
chamada de linguagem Turing-reconhecível.
• Na Teoria da Computabilidade, tradicionalmente
chamada Teoria da Recursão, um conjunto S de
números naturais é chamado recursivamente
enumerável, computavelmente enumerável,
semi-decidível, demonstrável ou Turing-
reconhecível, se é aceito por uma Máquina de
Turing.
• O modelo matemático conhecido como Máquina de
Turing, consiste basicamente de três partes: Fita,
Unidade de Controle e Programa ou Função de
Transição.
• A Fita é usada simultaneamente como dispositivo
de entrada, saída e memória de trabalho.
• A Unidade de Controle reflete o estado corrente da
máquina (estado ativo). Possui uma unidade de
leitura e gravação (cabeça da fita) a qual acessa
uma célula da fita de cada vez e movimenta-se para
a esquerda ou direita.
• O Programa, Função Programa ou Função de
Transição é uma função que comanda as leituras e
gravações, o sentido de movimento da cabeça e
define o estado da máquina.
Observação:
• A fita é finita à esquerda e infinita à direita (tão
grande quanto necessário), sendo dividida em
células, cada uma armazenando um símbolo, que
podem:
✓ Pertencer ao alfabeto de entrada.
✓ Pertencer ao alfabeto auxiliar.
✓ Ser “branco”.
✓ Ser “marcador de inicio de fita”.
Configuração Inicial
• Inicialmente, a palavra a ser processada (ou seja, a
informação de entrada para a máquina) ocupa as
células mais à esquerda após o marcador de inicio
da fita, ficando as demais com “branco”.
Configuração Inicial
a b b c
Fita
Marcador de inicio da Fita
Entrada
Branco
Unidade de Controle
Posiciona na 
Cabeça da FitaControle
   ...
Definição: Uma Máquina de Turing (MT) é uma 8-upla
M = (K,Σ, , q0, F, V, ,). onde:
• K (ou Q) é um conjunto finito não vazio de estados.
• Σ é o alfabeto de entrada.
•  é uma função programa, função de transição.
• qo (ou s) ∈ K é o estado inicial do autômato.
• F⊂ K é o conjunto de estados finais (aceitação).
• V é um alfabeto auxiliar (pode ser vazio).
•  é o símbolo espacial branco.
•  (ou ) é o símbolo de início ou marcador de
início da fita.
Observações
• O símbolo de início de fita ocorre exatamente uma
vez e na célula mais à esquerda da fita, auxiliando
na identificação de que a cabeça da fita encontra-se
na célula mais à esquerda da fita.
• A função programa considera o estado corrente
(ativo) e o símbolo lido da fita para determinar o
novo estado, o símbolo a ser gravado e o sentido
de movimento da cabeça, sendo que esquerda e
direita serão representados por E e D,
respectivamente.
• A função programa pode ser interpretada como um
diagrama, como ilustrado na figura a seguir.
Supondo a transição (p,x)=(q,y,m).
(x, y, m)
p q
Estado
Anterior
Novo
Estado
Símbolo lido
da Fita (entrada)
Sentido de 
Movimento
Símbolo 
Gravado
Computação
• A computação de uma Máquina de Turing M, para
uma palavra de entrada w, consiste na sucessiva
aplicação da função programa a partir do estado
inicial e da cabeça posicionada na célula mais à
esquerda fita até ocorrer uma condição de parada.
• O processamento de M para a entrada w pode
parar ou ficar processando indefinidamente (ciclo
ou loop infinito).
Parada
A parada do processamento de uma Máquina de
Turing M, para a entrada w pode ser feita de duas
maneiras:
• Aceita a entrada w. Atinge um estado final: a
máquina para, e a palavra w é aceita.
Parada
• Rejeita a entrada w. São duas possibilidades:
✓ A função programa é indefinida para o
argumento (símbolo lido e estado corrente): a
máquina para, e a palavra w é rejeitada.
✓ O argumento corrente da função programa
define um movimento à esquerda, e a cabeça da
fita já se encontra na célula mais à esquerda: a
máquina para, e a palavra w é rejeitada.
http://www.google.com/doodles/alan-turings-100th-birthday
• Exemplo: Máquina de Turing: Duplo
balanceamento.
• Considere a linguagem L = {anbn | n  0}.
• Sendo:
M = ({a,b},{q0,q1,q2,q3,q4},,{q4},{A,B}, ,)
• Vamos verificar como se dá o processamento para a
entrada w = aabb para a Máquina de Turing M
representada na máquina de estado a seguir.
• Exemplo: Processamento para a entrada w = aabb.
(q0,)=(q0,,D)
• Exemplo: Processamento para a entrada w = aabb..
(q0,a)=(q1,A,D)
• Exemplo: Processamento para a entrada w = aabb..
Logo, a entrada w = 
aabb é reconhecida 
(aceita) pela Máquina 
de Turing M.
(q3,B)=(q3,B,D)
• Exemplo: Processamento para a entrada w = aabb..
Professor
Me. Paulo David
pd.mnpa@gmail.com
Faculdade Maurício de Nassau
Curso: Sistemas de Informação 
Disciplina: Linguagens Formais e Autômatos
Professor: Me. Paulo Roberto Sousa David
Máquina de Turing