TEORIA DA COMPUTAÇÃO-TESTE DE CONHECIMENTO-08

Prévia do material em texto

11/3/21, 9:45 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=55849662&user_cod=2828661&matr_integracao=202004135813 1/3
Teste de
Conhecimento
 avalie sua aprendizagem
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?
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
TEORIA DA COMPUTAÇÃO
Lupa   Calc.
   
   
CCT0832_A8_202004135813_V1 
 
Aluno: ALESSANDRO VIANA DE ARAUJO Matr.: 202004135813
Disc.: TEORIA DA COMPUTAÇÃO  2021.3 EAD (G) / EX
 
Prezado (a) Aluno(a),
 
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua avaliação. O
mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se familiarizar com este
modelo de questões que será usado na sua AV e AVS.
 
1.
Anda para a direita até encontrar um 1, substitui por 0 e para. 
Substitui todos os 0¿s por 1¿s na fita.
Anda para a direita indefinidamente, sem modificar a fita.
Para assim que encontrar um 0.
Substitui todos os 1¿s por 0¿s na 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.
 
 
 
 
2.
O conjunto de símbolos usados pela máquina de Turing é infinito. 
Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma condição de parada. 
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. 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas. 
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.
 
 
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
11/3/21, 9:45 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=55849662&user_cod=2828661&matr_integracao=202004135813 2/3
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, 
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
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
 
 
 
Explicação:
.
 
 
 
 
3.
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona, fornecendo
respostas aproximadas.
 
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.
 
existe algoritmo exato de tempo de execução polinomial para solucioná-lo.
 
não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
 
 
 
 
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.
regulares. 
livres do contexto. 
sem restrição.
 
irregulares. 
sensíveis ao contexto. 
 
 
 
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
 
 
 
 
5.
A memoria
O programa
11/3/21, 9:45 PM Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=55849662&user_cod=2828661&matr_integracao=202004135813 3/3
Qual das seguintes afirmações é falsa?
 
A fita
A unidade de controle
 
O processador
 
 
 
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.
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
 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.
 
 
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
 
 
 
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.
 
 
 
 
 
 
 
    Não Respondida      Não Gravada     Gravada
 
 
Exercício inciado em 03/11/2021 21:42:30. 
 
 
 
 
javascript:abre_colabore('34918','271368075','4962024279');