Exercícios de Teoria da Computação

Prévia do material em texto

Universidade Federal de Lavras 
Departamento de Ciência da Computação 
2
o
 semestre de 2011 
 
 
GCC108 – Teoria da Computação 
Professor Responsável: Leonardo Andrade Ribeiro 
 
 
Avaliação: Exercícios 1 
Data: 08.09.2011 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
Aluno:_________________________________Matrícula:_____________ Nota:____ 
 
 
Nomenclatura: 
 
AFD - Autômato Finito Determinístico 
AFND - Autômato Finito Não-Determinístico 
MT - Máquina de Turing 
 
 
 
 
Questão 1 – Automâtos Finitos 
 
a) Qual é a linguagem do AFND abaixo? 
 
 
 
 
 
b) Construa um AFD que aceite qualquer palavra sobre o alfabeto {0,1}, com 
exceção de 00 e 000. 
 
c) Construa um AFND aceite qualquer palavra sobre o alfabeto {0,1} que possua 
00 como sufixo. O AFND deve conter no máximo três estados. 
 
 
d) Construa um AFD que seja equivalente ao AFND representado abaixo. Indique 
no AFD resultante os estados desnecessários, se houver; Alternativamente, o 
aluno poderá apresentar o AFD resultante e sua versão simplificada 
separadamente. 
 
 
q
0
 q
1
 
0,1 
1 
AFND 
𝜀 
 
a) Questa 2 – Máquinas de Turing (Nos exercícios abaixo, as MTs podem ser 
descritas em diagrama de estados ou em alto-nível) 
 
b) Construa 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. A máquina poderá conter uma ou duas fitas. 
 
 
 
c) Considere a MT abaixo. Apresente a sequência de configurações desta MT para as 
seguintes palavras de entrada: 
 
i. 11 
ii. 1#1 
iii. 1##0 
iv. 10#01 
 
 
 
 
 
d) Construa uma MT de uma fita que mova a palavra de entrada uma posição para a 
direita na fita e termine com a cabeça na posição inicial, isto é, configuração inicial 
q0entrada˽ e configuração final q0˽entrada˽. 
 
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” 
Escreva buffer-fita = copie símbolo do buffer para a posição atual da cabeça le 
 
 
e) Do exercício anterior, explique informalmente, mas claramente, como o objeto e 
as operações adicionais poderiam ser representadas em um diagrama de estados. 
 
 
f) Construa uma MT de duas fitas que, dada a palavra de entrada , escreva 
onde é a palavra reversa de . 
 
Configuração inicial: q0p˽. Configuração final: q0p 
 ˽ 
 
 
 
g) Construa uma MT de uma fita que decida a seguinte linguagem: 
L = { p | contém um número igual de 0„s e 1‟s} 
 
 
h) Defina linguagem Turing-Decidível e linguagem Turing-Reconhecível? Neste 
contexto, explique porque toda linguagem Turing-Decidível é também Turing-
Reconhecível, mas nem toda linguagem Turing-Reconhecível é Turing-Decidível. 
 
 
 
 
 
 
 
 
 
Questa 3 – Decidibilidade 
a) Descreva informalmente, mas claramente, a prova para o problema da parada 
usando a dicotomia Pára/Loop 
 
b) Apresente informalmente, mas claramente, a idéia para a prova do seguinte 
Teorema: Se uma linguagem é Turing-reconhecível e seu complemento ̅ 
também é Turing-reconhecível, então é Turing-decidível.