CCT0832 - Teste de conhecimento - Aula 8

Prévia do material em texto

1
        Questão
	
	
	Considere a máquina de Turing descrita pelas seguintes  regras, iniciando no estado q0:
(q0, 0)  (q0, 0, D)
(q0, 1)  (q1, 0, D)
(q2, 0)  (q2, 1, D)
O que essa máquina faz?
		
	
	Substitui todos os 0¿s por 1¿s na fita.
	
	Substitui todos os 1¿s por 0¿s na fita.
 
	
	Anda para a direita indefinidamente, sem modificar a fita.
	 
	Anda para a direita até encontrar um 1, substitui por 0 e para. 
	
	Para assim que encontrar um 0.
	Respondido em 15/03/2021 17:13:38
	
Explicação:
A máquina inicia no estado q0. Se ela ler um 0,continua em q0 e anda para a direita, conforme a primeira regra.
Se ela ler um 1, ela o substitui por 0, muda para o estado q1 e vai para a direita, conforme a segunda regra. Como não existe regra que trate o estado q1, a máquina para. 
Logo, a alternativa d está correta.
	
	
	 
		2
        Questão
	
	
	No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
		
	 
	Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma condição de parada. 
	
	O conjunto de símbolos usados pela máquina de Turing é infinito. 
	
	Uma máquina de Turing pode alterar várias entradas em cada vez, pois ela é capaz de transferir sua atenção para mais de uma posição da fita em cada argumento da função de transição.
 
 
	
	As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas. 
	
	A máquina em questão registra o valor da palavra de entrada e depois pára, quando a função indicar um movimento da cabeça para a esquerda e ela já se encontrar no início da fita. 
	Respondido em 15/03/2021 17:14:53
	
Explicação:
.
	
	
	 
		3
        Questão
	
	
	O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim descrito: determinar, para quaisquer máquinas de Turing M e palavra w, se M irá eventualmente parar com entrada w.
Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o algoritmo termina ou se executará indefinidamente.
Para o problema da parada, 
		
	
	existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
 
	
	 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo respostas aproximadas.
 
	 
	não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
 
	
	existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
 
	
	 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial que o soluciona, fornecendo respostas aproximadas.
 
	Respondido em 15/03/2021 17:15:27
	
Explicação:
O problema da parada pode ser definido como:
Seja S o conjunto de todos os pares (A,D), em que A é um algoritmo, e D, dado de entrada; (A,D) tem a propriedade P se o algoritmo A, quando recebe o dado D, eventualmente produz um resultado (ou seja, eventualmente para) A tese de Church-Turing mostra que o problema da parada é não decidível, ou seja, não existe um algoritmo H tal que para todo (A,D) que pertence à S: H(A,D)= { 1 se A(D) eventualmente para; 
0 caso contrário 
A prova informal de que tal H não existe é obtida por contradição.
Suponha que H existe. Seja C o algoritmo: ¿entrada A; executa H(A,A); se H(A,A)=0, então, retorna 1, senão entra em loop¿.
Então, ∀A,(H(A,A)=0 ⇿ ¬A(A) eventualmente para ⇿ H(A,A)=0) (pois H é função total) e ∀A,(H(A,A)=0 ⇿ ¬A(A) eventualmente para).
Tomando A como sendo C, obtemos que C(C) eventualmente para, se e somente se ¬C(C) eventualmente para, e isto é uma contradição!
Logo, não existe um algoritmo que solucione o problema.
As respostas das alternativas A e B não estão corretas, pois afirmam que existe um algoritmo que resolve o problema.
As respostas das alternativas D e E não estão corretas, pois afirmam que existe um algoritmo de aproximação e, pelo exposto na justificativa da resposta correta, tal algoritmo não existe.
	
	
	 
		4
        Questão
	
	
	Correlacionando a hierarquia de Chomsky com os reconhecedores de linguagem, é correto afirmar que a máquina de Turing, tradicional ou básica, corresponde às gramáticas
		
	
	livres do contexto. 
	
	sensíveis ao contexto. 
	
	irregulares. 
	 
	sem restrição.
 
	
	regulares. 
	Respondido em 15/03/2021 17:15:58
	
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
	
	
	 
		5
        Questão
	
	
	Na máquina de turing o componente que contem o estado corrente da máquina é:
 
		
	
	A fita
	
	A memoria
	
	O processador
	 
	A unidade de controle
 
	
	O programa
	Respondido em 15/03/2021 17:16:26
	
Explicação:
UNIDADE DE CONTROLE ¿ Contém o estado corrente da máquina, lê ou escreve dados na fita e pode se mover para a ¿frente¿(direita) ou para ¿trás¿(esquerda)
	
	
	 
		6
        Questão
	
	
	Qual das seguintes afirmações é falsa?
 
		
	
	 Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a computação de M com entrada w vai ou não parar.
 
	
	 O problema da parada é indecidível.
 
	
	
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
	
	Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
	 
	 Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
 
	Respondido em 15/03/2021 17:17:18
	
Explicação:
(A) Dada uma máquina de Turing M com alfabeto de entrada Σ e uma string w∈Σ, não se sabe se a computação de M com entrada w vai ou não parar.
(B) O problema da parada é indecidível.
(C) Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
(D) Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
(E) Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
A única alternativa falsa é a D. Linguagens regulares são reconhecidas por autômatos finitos determinístico e, pela hierarquia de Chomsky, toda linguagem regular também é livre de contexto.