Teoria da Computação - AVP03

Prévia do material em texto

04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 1/4
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): JOSEILDON DA SILVA DANTAS 201908040459
Acertos: 3,0 de 10,0 04/06/2020
Acerto: 1,0 / 1,0
Um grupo de objetos representado como uma unidade é chamado de:
 Conjunto
Membro
Complemento
Elemento
Operação
Respondido em 04/06/2020 10:17:50
Acerto: 0,0 / 1,0
Um grafo consiste num conjunto de nós (ou vértices) e num conjunto de arcos (ou arestas). É correto afirmar
que o grau de um nó é
 a distância entre este nó e um outro nó qualquer do grafo.
 o número de arcos incidentes nesse nó.
o número de pares ordenados que formam o arco.
 
a posição deste nó em relação ao nó raiz do grafo
 um número associado ao arco, também chamado de peso.
Respondido em 04/06/2020 10:17:52
Acerto: 0,0 / 1,0
Entre os diversos tipos de árvores, a árvore enraizada se caracteriza por:
 Não apresentar um vértice (raiz) que se distingue dos demais.
Um grafo acíclico, não orientado e conectado.
Um grafo acíclico, não orientado mas, possivelmente desconectado.
 Um tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais
Uma estrutura de vértices que é definida por meio de um conjunto de vértices.
Respondido em 04/06/2020 10:17:53
Acerto: 0,0 / 1,0
 Questão1
a
 Questão2
a
 Questão3
a
 Questão4
a
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 2/4
Quanto aos automatos deterministicos podemos afirmar que:
 Pode estar em muitos estados ao mesmo tempo.
 Para cada estado e para cada entrada só há zero ou uma transição possível
 
Não é representado por uma quíntupla
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis.
É um autômato que permite zero, uma ou mais transições a partir de um estado e para um mesmo
símbolo de entrada.
Respondido em 04/06/2020 10:17:54
Acerto: 0,0 / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
 os simbolos de entrada
 o estado inicial
 
as transições
o conjunto de estados finais
O número de estados
Respondido em 04/06/2020 10:17:55
Acerto: 0,0 / 1,0
Considere as seguintes expressões regulares cujo alfabeto é {a,b}.
 R1 = a(a ∪ b)*
 R2 = b(a ∪ b)*
Se L(R) é uma linguagem associada a uma expressão regular R, é correto afirmar que
 
 Um autômato finito não determinístico que reconheça L(R1) ∪ L(R2) tem, pelo menos, quatro estados.
 
 
 Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
L(R1) = L(r2) 
Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem
infinita.2). 
L(R2) = {w | w termina com b}
Respondido em 04/06/2020 10:17:57
Acerto: 0,0 / 1,0
Sobre a hierarquia de Chomsky podemos afirmar que: 
 Uma linguagem que não é regular é livre de contexto
 
 As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem
 
 As linguagens reconhecidas por autômatos a pilha são as linguagens regulares
 Há linguagens que não são nem livres de contexto nem sensíveis ao contexto
 
Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular
 
 Questão5
a
 Questão6
a
 Questão7
a
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 3/4
 
Respondido em 04/06/2020 10:17:58
Acerto: 0,0 / 1,0
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. 
 sem restrição.
 
regulares. 
irregulares. 
sensíveis ao contexto. 
Respondido em 04/06/2020 10:17:42
Acerto: 1,0 / 1,0
Considere a gramática a seguir, em que S, A e B são símbolos não terminais, 0 e 1 são terminais e ε é a cadeia
vazia.
S-> 1S|0A|ε
A-> 1S|0B|ε
B-> 1S|ε
A respeito dessa gramática, analise as afirmações a seguir.
I. Nas cadeias geradas por essa gramática, o último símbolo é 1.
II. O número de zeros consecutivos nas cadeias geradas pela gramática é, no máximo, dois.
III. O número de uns em cada cadeia gerada pela gramática é maior que o número de zeros.
IV. Nas cadeias geradas por essa gramática, todos os uns estão à esquerda de todos os zeros.
É correto apenas o que se afirma em
 II.
III e IV.
 
I.
II e IV.
I e III.
Respondido em 04/06/2020 10:17:43
Acerto: 1,0 / 1,0
Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema
pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à
complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.
I. A descoberta do cientista implica que P = NP
PORQUE
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-
Completos.
A respeito dessas asserções, assinale a opção correta.
 
 
 As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I.
 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
 
As asserções I e II são proposições falsas.
 
 Questão8
a
 Questão9
a
 Questão10
a
04/06/2020 Estácio: Alunos
simulado.estacio.br/alunos/ 4/4
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 
Respondido em 04/06/2020 10:18:03
javascript:abre_colabore('38403','198509884','3985884943');