trabFinal_Mateus

Prévia do material em texto

Pontifícia Universidade Católica de Minas Gerais 
Programa de Pós-graduação em Informática 
 Fundamentos Teóricos da Computação 
Prof. Mark Alan Junho Song 
 
Máquina de Turing 
 
 
 
Questão 1. Construa máquinas de Turing que aceitem: 
 
a. L = { aib2i | i > 0 } 
 
 
b. L = { aibjck | j = i+k } 
 
 
 
c. L = { w  { a, b }* tal que o número de a´s é igual ao número de b´s } 
 
d. L = { w  { a, b }* tal que o número de a´s é o dobro do número de b´s } 
 
e. L = { w  { a, b }* tal que o número de a´s não é o dobro do número de b´s } 
 
 
 
Questão 2. Construa máquinas de Turing que enumerem: 
 
a. L = { aib2i | i > 0 } 
 
b. L = { a(2i-1)b2i | i > 1 } 
 
 
 
Questão 3. Construa máquinas de Turing que: 
 
a. copiem um string w  { a, b }* para a fita trocando todo os a’s por b e todos os 
b’s por a. 
 
 
Pontifícia Universidade Católica de Minas Gerais 
Programa de Pós-graduação em Informática 
 Fundamentos Teóricos da Computação 
Prof. Mark Alan Junho Song 
 
 
b. copiem o reverso de um string w  { a, b }* para a fita. 
 
c. verifiquem se w  { a, b, c }* é palíndromo. 
 
 
 
 
Pontifícia Universidade Católica de Minas Gerais 
Programa de Pós-graduação em Informática 
 Fundamentos Teóricos da Computação 
Prof. Mark Alan Junho Song 
 
 
 
 
Lema do bombeamento: 
 
Questão 6. Prove usando o pumping lemma que as seguintes linguagens não são livres de 
contexto: 
a. { anbnanbn | n > 0 } 
b. { 0n12n2n | n > 0 } 
c. { wwRw | w  { a, b }* } 
 
Decidibilidade 
 
 
 
 
Verifique se as seguintes linguagens são decidíveis: 
 
 
1. L = { <A> | A é um DFA que reconhece * }. 
 
 
2. L = { <A,w> | A é um DFA que reconhece w  * }. 
 
Decidível. Exemplo: 
 
 
Pontifícia Universidade Católica de Minas Gerais 
Programa de Pós-graduação em Informática 
 Fundamentos Teóricos da Computação 
Prof. Mark Alan Junho Song 
 
 
 
3. L = { <A,B> | A,B DFA’s tal que L(A)  L(B) }. 
Decidível 
 
4. L = { <A,B> | A,B DFA’s tal que L(A)  L(B) }. 
Decidível 
 
 
5. L = { <G> | G uma gramática livre de contexto tal que   L(G) }. 
Decidível