Salve - Aula 08 - Teoria da Computação - Teste de Conhecimento

Prévia do material em texto

TEORIA DA COMPUTAÇÃO
8a aula
 Lupa 
PPT MP3
 
 
 1a Questão
Qual das seguintes afirmações é falsa?
 
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
 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 autômato finito determinístico que reconheça alguma linguagem livre de contexto.
 
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
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.
 
 2a 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 exponencial que o
soluciona, fornecendo respostas aproximadas.
 
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:abre_frame('2','8','','','');
javascript:abre_frame('3','8','','','');
 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.
 
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.
 
 3a Questão
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
A memoria
 A unidade de controle
 
A fita
O processador
O programa
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)
 
 4a 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.
 Anda para a direita até encontrar um 1, substitui por 0 e para. 
Para assim que encontrar um 0.
Substitui todos os 1¿s por 0¿s na fita.
 
Anda para a direita indefinidamente, sem modificar a fita.
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.
 
 5a 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
sensíveis ao contexto. 
irregulares. 
regulares. 
livres do contexto. 
 sem restrição.
 
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
 
 6a Questão
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
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. 
 Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma
condição de parada. 
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.
 
 
O conjunto de símbolos usados pela máquina de Turing é infinito. 
Explicação:
.
javascript:abre_colabore('38403','194088940','3875673654');