Resolução EE3 2009.2

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

1.
(i) Verdadeiro. O Teorema 4.22 do livro (Sipser) afirma que "Uma linguagem é decidível sse ela é Turing-reconhecível e co-Turing-reconhecível". Se o complemento de L não é Turing-reconhecível (= L não é co-Turing-reconhecível), L não pode ser decidível.
(ii) Verdadeiro. Seja M1 uma decisora para L1, e M2 uma decisora para L2. Vamos criar a máquina M, que decide L1oL2:
M = "Sobre a entrada w1w2...wn:
	1. Para i = 1 até n+1:
	2.	Rode M1 sobre w1...wi-1. (tome w1w0 = cadeia vazia)
	3.	Rode M2 sobre wi...wn. (tome wn+1wn = cadeia vazia)
	4.	Se M1 e M2 aceitarem, aceite, se alguma das duas rejeitarem, continue.
	5. Se terminar o loop e M não aceitou, rejeite."
Essa MT divide a entrada w de todas as formas possíveis em duas partes, e testa exaustivamente se essas duas partes pertencem a L1 e L2 respectivamente. Ela nunca vai entrar em loop infinito pois M1 e M2 são decisoras. Caso haja alguma divisão de w de modo que a primeira parte pertença a L1 e a segunda pertença a L2, a máquina aceita.
(iii) Falso. Contra-exemplo: digamos L não seja decidível, mas seja reconhecível. Pelo Teorema 3.21 do livro (Sipser) existe um enumerador para L, contradizendo, assim, a afirmação da questão.
2.
(i) Verdadeiro. Seja a linguagem L1 = {<A>| A é um AFD e L(A) contém alguma cadeia que começa com 0 e termina com 1}. Seja T uma decisora que decide Vafd (Teorema 4.4 do Sipser).
Vamos construir a MT M1 que decide L1:
M1 = "Sobre a entrada <A>, onde A é um AFD:
	1. Construa um AFD B onde L(B) = L(A) ∩ 0∑*1
	2. Rode a MT T sobre B.
	3. Se T aceita, rejeite; se T rejeita, aceite"
obs. A construção do passo 1 pode ser feita convertendo a ER 0∑*1 para um AFN C. Em seguida, construa um AFN B' que reconhece a interseção de L(A) e L(C). Por fim, converta B' para um AFD B.
(ii) Verdadeiro. Seja a linguagem L2 = {<A>| A é um AFD e L(A) é uma linguagem infinita}. A seguinte MT decide L2:
M2 = "Sobre a entrada <A>, onde A é um AFD:
	1. Seja k o número de estados de A.
	2. Construa um AFD B que aceite todas as cadeias de comprimento k ou mais.
	3. Construa um AFD C tal que L(C) = L(A) ∩ L(B).
	4. Rode a MT T, que decide Vafd, sobre C.
	5. Se T aceita, rejeite; se T rejeita, aceite."
(iii) Verdadeiro. A prova é por contradição. Seja a linguagem L3 = {<M,w,q> | M é uma MT, w é uma cadeira, q é um estado de M; e quando M roda sobre w, passa pelo estado q}. Supondo uma MT Q que decide L3, vamos construir uma decisora para Amt:
M3 = "Sobre a entrada <M,w>, onde M é uma MT e w uma cadeia:
	1. Rode Q sobre a entrada <M,w,qaceita>, onde qaceita é o estado de aceitação de M.
	2. Se Q aceita, aceite; caso contrário, rejeire."
(iv) Falso. Seja L4 = {<G>| G é uma GLC sobre {0,1}* e 1* ∩ L(G) ≠ Ø}. Vamos construir uma MT que decide L4:
M4 = "Sobre a entrada <G>, onde G é uma GLC:
	1. Construra a GLC H tal que L(H) = 1* ∩ L(G).
	2. Rode a MT R, que decide Vglc, sobre H.
	3. Se T aceita, rejeite; se T rejeita, aceite."
obs. Pelo problema 2.18 do livro (Sipser), temos que a construção da linha 1, que consiste na interseção de uma LR com uma LLC, realmente produz uma linguagem livre-do-contexto, podendo assim ser gerada por uma GLC.
(v) Verdadeiro. L = {<G,x>| G é uma GLC que gera alguma cadeia w da qual x é uma subcadeia}. Vamos criar uma MT que decide L:
M5 = "Sobre a entrada <G,x>, onde G é uma GLC e x uma cadeia:
	1. Construa a GLC H tal que L(H) = ∑*x∑* ∩ L(G).
	2. Rode a MT R, que decide Vglc, sobre H.
	3. Se T aceita, rejeite; se T rejeita, aceite."
(vi) Verdadeiro. L = {<M>| M rejeita pelo menos duas cadeias de comprimento par}. Seja s1,s2,s3.. uma lista de todas as cadeias de tamanho par de ∑*. Vamos criar uma MT que decide L:
M6 = "Sobre a entrada <M>, onde M é uma MT:
	1. Repita o seguinte para i = 1,2,3,...
	2. 	Rode M por i passos sobre cada entrada s1,s2,...,si.
	3.	Se pelo menos duas computações rejeitam, aceite."
3.
(i) Verdadeiro. Temos que Amt ≤m REGmt (Amt é redutível por mapeamento a REGmt). Negando dos dois lados, temos que Amt' ≤m REGmt'. Como Amt' é indecidível, temos, pelo Corolário 5.23 (Sipser) que REGmt' é indecidível.
(ii) Falso. Seja EQglc = {<G1,G2> | G1 e G2 são GLCs e L(G1) = L(G2)}. Mostramos uma redução de TODASglc para EQglc:
M2 = "Sobre a entrada <G>:
	1. Construa uma GLC G' tal que L(G') = ∑*.
	2. Rode a MT R que decide EQmt sobre a entrada <G,G'>.
	3. Se R aceita, aceite, caso contrário, rejeite."
Como TODASglc é indecidível (teorema 5.13, Sipser), EQglc também é.
ou, usando redução por mapeamento (TODASglc ≤m EQglc):
F = "Sobre a entrada <G>:
	1. Construa uma GLC G' tal que L(G') = ∑*.
	2. Retorne <G,G'>"
Se L(G) = ∑*, a função retorna duas cadeias iguais. Se L(G) != ∑*, as duas cadeias são diferentes. Portanto, a redução funciona como o desejado.
(iii) Verdadeiro. Podemos criar uma reconhecedora para A da seguinte forma:
M3 = "Sobre a entrada w:
	1. Rode R sobre f(w), onde f é a função de redução de A para B e R é a reconhecedora de B.
	2. Aceite, se R aceitar."
(iv) Verdadeiro. Pelo Corolário 5.29 do livro-texto (Sipser).
(v) Falso. L não é co-Turing-reconhecível. Vamos fazer isso mostrando que Amt' ≤m L' (ou seja, Amt ≤m L):
F = "Sobre a entrada <M,w>:
	1. Construa a seguinte máquina:
		M' = "Sobre a entrada x:
		1.	Se x != <M'>, rejeite.
		2.	Se x = <M'>, rode M sobre w.
		3.	Se M aceita, aceite, caso contrário, rejeite."
	2. Dê como saída <M'>."
(vi) Falso. É ao contrário, o problema de aceitação de palavras por máquina de Turing é redutível por mapeamento ao problema da correspondência de Post.
4.
(i) Indefinido. O problema NP = co-NP ainda é um problema em aberto.
(ii) Falso. Os problemas da classe P possuem o complemento em P.
(iii) Falso. B pode ser o problema SAT. Assim, A é redutível a B pois todos os problemas em NP o são.
(iv) Verdadeiro. Por transitividade, todos os problemas em NP seriam redutíveis a B.
(v) Indefinido. O problema do isomorfismo de grafos é um dos poucos problemas em NP que ainda não se sabe ser solúvel em tempo polinomial nem NP-completo.
(vi) Verdadeiro. O custo para construir a fórmula booleana é O(n^2k), onde n é o tamanho da entrada w.
5.
(i) Falso. O teorema de Savitch mostra e PSPACE = NPSPACE.
(ii) Falso. Pelo mesmo teorema, sabemos que a determinística decide na verdade em tempo f(n)^2.
(iii) Falso. NL = coNL.
(iv) Falso. O teorema mostra que a simulação pode ser feita com uma máquina determinística de ESPAÇO polinomial.
(v) Verdadeiro. Pelo Teorema 8.25 do livro.
(vi) Verdadeiro. A classe SPACE é fechada sob complementação. Como o teorema de Savitch mostra que NSPACE(f(n)) = SPACE(f(n)^2), temos que NSPACE também é fechada sob complementação.