Teoria da Computação 5

Prévia do material em texto

Painel / Meus cursos / TCADS / 📝 AVALIAÇÕES 2024/4 / ATIVIDADE ONLINE 2 - AV22024/4
Iniciado em terça, 29 out 2024, 14:30
Estado Finalizada
Concluída em terça, 29 out 2024, 14:43
Tempo
empregado
12 minutos 51 segundos
Avaliar 1,60 de um máximo de 2,00(80%)
Questão 1
Incorreto
Atingiu 0,00 de 0,20
Considere as seguintes afirmativas:
I.Toda linguagem recursivamente enumerável é indecidível.
II.Toda linguagem regular é decidível.
III.Não existem linguagens recursivamente enumeráveis que não são computáveis.
Assinale a alternativa correta.
Escolha uma opção:
a. Somente as afirmativas II e III estão corretas.
b. Somente as afirmativas I e II estão corretas. 
c. Somente as afirmativas I e III estão corretas.
d. Todas as afirmativas estão corretas.
e. Nenhuma das afirmativas está correta.
29/10/2024, 14:43 ATIVIDADE ONLINE 2 - AV22024/4
https://moodle.ead.unifcv.edu.br/mod/quiz/review.php?attempt=4617834 1/6
https://moodle.ead.unifcv.edu.br/my/
https://moodle.ead.unifcv.edu.br/my/
https://moodle.ead.unifcv.edu.br/course/view.php?id=2987
https://moodle.ead.unifcv.edu.br/course/view.php?id=2987#section-4
https://moodle.ead.unifcv.edu.br/mod/quiz/view.php?id=221772
Questão 2
Correto
Atingiu 0,20 de 0,20
Máquinas de Turing não determinísticas (MTND) são máquinas de Turing (MT) cuja função de
transição gera um conjunto finito de possíveis estados.
Leia as afirmações a seguir sobre MTND. Depois, assinale a alternativa correta.
I. O não determinismo aumenta a quantidade de linguagens que uma MT padrão reconhece.
II. Uma MTND pode ser simulada a partir de uma MT padrão.
III.Uma MTND reconhece as linguagens recursivamente enumeráveis.
Escolha uma opção:
a. Apenas a afirmação III está correta.
b. Apenas as afirmações I e II estão corretas.
c. Todas as afirmações estão corretas.
d. Apenas as afirmações II e III estão corretas. 
e. Apenas as afirmações I e III estão corretas.
Questão 3
Correto
Atingiu 0,20 de 0,20
As linguagens sensíveis ao contexto são geradas por quais gramáticas?
Escolha uma opção:
a. Gramáticas livres ao contexto.
b. Gramáticas de Turing.
c. Gramáticas irrestritas.
d. Gramáticas regulares.
e. Gramáticas sensíveis ao contexto. 
29/10/2024, 14:43 ATIVIDADE ONLINE 2 - AV22024/4
https://moodle.ead.unifcv.edu.br/mod/quiz/review.php?attempt=4617834 2/6
Questão 4
Incorreto
Atingiu 0,00 de 0,20
Escolha uma opção:
a. 
b. 
c. 
d. 
e. 
29/10/2024, 14:43 ATIVIDADE ONLINE 2 - AV22024/4
https://moodle.ead.unifcv.edu.br/mod/quiz/review.php?attempt=4617834 3/6
Questão 5
Correto
Atingiu 0,20 de 0,20
Considere a lista de gramáticas (coluna 1) e a lista de máquinas que reconhecem gramáticas
(coluna 2):
Relacione a gramática à sua máquina reconhecedora e, em seguida, assinale a alternativa que
apresenta a sequência correta.
Escolha uma opção:
a. a-4, b-3, c-2, d-1. 
b. a-2, b-3, c-1, d-2.
c. a-3, b-2, c-4, d-1.
d. a-1, b-3, c-2, d-4.
e. a-4, b-2, c-1, d-3.
Questão 6
Correto
Atingiu 0,20 de 0,20
Uma gramática do Tipo 0 é uma:
Escolha uma opção:
a. Gramática irrestrita. 
b. Gramática sensível ao contexto.
c. Gramática regular.
d. Gramática linear à esquerda.
e. Gramática livre de contexto.
29/10/2024, 14:43 ATIVIDADE ONLINE 2 - AV22024/4
https://moodle.ead.unifcv.edu.br/mod/quiz/review.php?attempt=4617834 4/6
Questão 7
Correto
Atingiu 0,20 de 0,20
Analise as seguintes afirmações sobre complexidade e assinale V para verdadeiro e F para
falso em cada uma delas. Em seguida, assinale a alternativa com a sequência correta.
( ) Um problema intratável não pode ser resolvido por uma máquina de Turing.
( ) Problemas tratáveis são aqueles cuja resolução termina em tempo hábil.
( ) O problema do caixeiro viajante é intratável.
Escolha uma opção:
a. V - F - V
b. F - F - F
c. F - V - V 
d. V - V - V
e. F - V - F
Questão 8
Correto
Atingiu 0,20 de 0,20
Leia a afirmação a seguir:
"Qualquer função computável pode ser calculada por uma máquina de Turing."
Essa afirmação é chamada de:
Escolha uma opção:
a. Tese de Church-Turing. 
b. Autômato linearmente limitado.
c. Definição de linguagens recursivamente enumeráveis.
d. Definição de máquinas de Turing.
e. Não determinismo.
29/10/2024, 14:43 ATIVIDADE ONLINE 2 - AV22024/4
https://moodle.ead.unifcv.edu.br/mod/quiz/review.php?attempt=4617834 5/6
Questão 9
Correto
Atingiu 0,20 de 0,20
As linguagens livres de contexto são aquelas que:
Escolha uma opção:
a. Não são ambíguas.
b. Podem ser reconhecidas por autômatos finitos determinísticos.
c. Podem ser geradas por meio de gramáticas regulares.
d. Podem ser geradas por meio de gramáticas livres de contexto. 
e. Possuem árvores de derivação diferentes.
Questão 10
Correto
Atingiu 0,20 de 0,20
Uma gramática linear à direita é uma gramática de qual tipo?
Escolha uma opção:
a. Tipo 3. 
b. Tipo 4.
c. Tipo 2.
d. Tipo 0.
e. Tipo 1.
29/10/2024, 14:43 ATIVIDADE ONLINE 2 - AV22024/4
https://moodle.ead.unifcv.edu.br/mod/quiz/review.php?attempt=4617834 6/6