TESTE 8

Prévia do material em texto

16/04/2023, 13:34 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/6
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?
TEORIA DA COMPUTAÇÃO
Lupa   Calc.
   
   
CCT0832_A8_202107065796_V1
Aluno: JUCELINO COSTA DE OLIVEIRA Matr.: 202107065796
Disc.: TEORIA DA COMPUTAÇÃO  2023.1 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.
Substitui todos os 0¿s por 1¿s na �ta.
Substitui todos os 1¿s por 0¿s na �ta.
 
javascript:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
16/04/2023, 13:34 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/6
No que concerne a utilização e o processamento de máquina de Turing, assinale a
opção correta.
 
Anda para a direita inde�nidamente, sem modi�car a �ta.
Para assim que encontrar um 0.
Anda para a direita até encontrar um 1, substitui por 0 e para. 
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.
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 �ta 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 �ta. 
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 é in�nito. 
Explicação:
.
16/04/2023, 13:34 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/6
Qual das seguintes a�rmações é falsa?
 
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
 
3.
 Não existe algoritmo que determina quando uma gramática livre de contexto
arbitrária é ambígua.
 
 O problema da parada é indecidível.
 
 Não existe autômato �nito 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.
 
 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.
 
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 �nito 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
�nitos determinístico e, pela hierarquia de Chomsky, toda linguagem regular também é
livre de contexto.
 
4.
A memoria
O processador
16/04/2023, 13:34 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/6
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 �nita, decidir se o algoritmo termina ou se executará
inde�nidamente.
Para o problema da parada, 
A �ta
O programa
A unidade de controle
 
Explicação:
UNIDADE DE CONTROLE ¿ Contém o estado corrente da máquina, lê ou escreve
dados na �ta e pode se mover para a ¿frente¿(direita) ou para ¿trás¿(esquerda)
 
5.
 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 exponencial para solucioná-lo.
 
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 polinomial que o soluciona, fornecendo respostas aproximadas.
 
não existe algoritmo que o solucione, não importa quanto tempo seja
disponibilizado.
 
Explicação:
O problema da parada pode ser de�nido como:
Seja S o conjunto de todos os pares (A,D), em que A é um algoritmo, e D, dado de
16/04/2023, 13:34 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/6
Correlacionando a hierarquia de Chomsky com os reconhecedores de linguagem, é
correto a�rmar que a máquina de Turing, tradicional ou básica, corresponde às
gramáticas
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 a�rmam que existe um
algoritmo que resolve o problema.
As respostas das alternativas D e E não estão corretas, pois a�rmam que existe um
algoritmo de aproximação e, pelo exposto na justi�cativa da resposta correta, tal
algoritmo não existe.
 
6.
irregulares. 
livres do contexto. 
regulares. 
sensíveis ao contexto. 
sem restrição.
 
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
16/04/2023, 13:34 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/6
    Não Respondida      Não Gravada     Gravada
Exercício inciado em 16/04/2023 13:32:47.
javascript:abre_colabore('35479','306275436','6186074200');