MTExercicios

Prévia do material em texto

Universidade Federal de Lavras 
Departamento de Ciência da Computação 
1
o
 semestre de 2012 
 
 
GCC108 – Teoria da Computação 
Professor Responsável: Leonardo Andrade Ribeiro 
 
Lista de Exercícios sobre Máquinas de Turing 
 
Em todos exercícios, o alfabeto é ∑ = {0,1} e as MTs deverão ser descritas em alto-nível e 
diagrama de estados, exceto quando outra requisição for mencionada explicitamente. Todas 
MTs deverão conter apenas uma fita, exceto quando outra definição for mencionada 
explicitamente. 
Nas descrições de alto-nível de MTs utilize as definições e convenções do documento 
específico sobre este tema. 
Nas descrições de MTs em forma de diagrama de estados, considere as seguintes convenções 
vistas em sala de aula: 
 É possível identificar o posicionamento da cabeça le no ínicio da fita e associar 
uma transição de estado com este evento. 
 É possível definir transições de estado que não movimentem a cabeça le, isto 
movimento N. Ex.: ( ) ( ) 
 
 
1) Projete uma MT que reconheça as seguintes linguagens: 
a. L = {p | p contém mais 0s do que 1s} 
b. L = {p | p contém duas vezes mais 0s do que 1s} 
c. L = {0n11n2| n1 e n2 > 0 e n1 = 2* n2} 
 
 
 
 
2) Projete uma MT que reconheça a seguinte linguagem: 
 
L = { }. 
 
Informalmente, nas palavras aceitas pela MT, cada deverá ser seguido por um 
número crescente de ’s. Descreva-a em alto-nível e em diagrama de estados. 
 
 
 
3) Projete uma MT de duas fitas que aceite palavras que são palíndromos. Descreva-a 
em diagrama de estados. 
 
 
4) Projete uma MT que reconheça a linguagem L = {#p%q%q#p | p, q ϵ {a,b}+}. Para a 
descrição em alto-nível, além das operações e objetos básicos vistos no curso, 
considere as seguintes definições adicionais. 
Objeto adicional: “buffer” com espaço para armazenar um símbolo. 
 
Operações adicionais: 
Escreva fita-buffer = copie o símbolo sob a cabeça le para o “buffer” 
Compare buffer-fita = compare o símbolo do buffer com o símbolo da posição atual 
da cabeça le 
 
Dica: A solução é simplificada se a palavra q for tratado primeiro. 
 
 
 
 
 
5) Defina os seguintes conceitos: 
a. Linguagem Turing-Decidível 
b. Linguagem Turing-Reconhecível 
c. Tese Church-Turing 
 
 
 
 
 
6) Considere a seguinte MT: 
M = “Na palavra de entrada p, onde p é a entrada é um polinômio definido sobre as 
variáveis inteiras x1, …, xk. 
Passo 1: Tente todas os possíveis arranjos de x1, …, xk. 
Passo 2: Avalie p em todos estes arranjos 
Passo 3: Se qualquer um destes resulta em 0, Aceite. Ou então, Rejeite.” 
 
a. M decide a linguagem formada por todos todos polinômios com raiz integral? 
Justifique sua resposta. 
b. M reconhece a linguagem formada por todos todos polinômios com raiz 
integral? Justifique sua resposta.