LINGUAGEM FORMAIS E AUTOMATOS-7

Prévia do material em texto

Exercícios sobre Máquinas de Turing 
 
 
Exercício 1: Projeto de Máquina de Turing 
Projete uma Máquina de Turing (MT) que reconheça a linguagem L={anbncn∣n≥0}. 
● Descreva formalmente a MT (conjunto de estados, alfabeto da fita, símbolo branco, 
função de transição, estado inicial, estados finais). 
● Explique a estratégia geral que sua MT utiliza para verificar se uma cadeia pertence 
a L. Por exemplo, como ela garante que o número de a's, b's e c's é o mesmo? 
 
Exercício 2: Rastreamento de Configuração 
Considere a seguinte Máquina de Turing M: 
● Q={q0 ,q1 ,q2 ,qf } (estados) 
● Σ={0,1} (alfabeto de entrada) 
● Γ={0,1,X,B} (alfabeto da fita, com B sendo o símbolo branco) 
● q0 é o estado inicial 
● qf é o único estado final 
● A função de transição δ é dada por: 
1. δ(q0 ,0)=(q1 ,X,D) (lê 0, escreve X, move para Direita) 
2. δ(q0 ,1)=(q0 ,1,D) (lê 1, escreve 1, move para Direita) 
3. δ(q0 ,B)=(qf ,B,D) (lê Branco, escreve Branco, move para Direita -> Aceita) 
4. δ(q1 ,1)=(q2 ,X,D) (lê 1, escreve X, move para Direita) 
5. δ(q1 ,0)=(q1 ,0,D) (lê 0, escreve 0, move para Direita) 
6. δ(q1 ,B)=(qf ,B,E) (lê Branco, escreve Branco, move para Esquerda -> Rejeita 
neste caminho, mas aqui para fins de parada) 
7. δ(q2 ,0)=(q2 ,0,D) (lê 0, escreve 0, move para Direita) 
8. δ(q2 ,1)=(q2 ,1,D) (lê 1, escreve 1, move para Direita) 
9. δ(q2 ,B)=(q0 ,B,E) (lê Branco, escreve Branco, move para Esquerda) 
Para a cadeia de entrada "010": 
● Descreva a sequência de configurações (IDs - Descrições Instantâneas) da MT, 
começando com q0 010. 
● A cadeia é aceita ou rejeitada? Qual o conteúdo final da fita quando a máquina 
para? 
● Utilize a ferramenta online para validar o processamento da máquina de Turing: 
https://morphett.info/turing/turing.html 
 
https://morphett.info/turing/turing.html
 
 
	Exercícios sobre Máquinas de Turing