Teoria da Computação

Prévia do material em texto

04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 1/5
 
 
Disc.: TEORIA DA COMPUTAÇÃO 
Aluno(a): YURI CID DA SILVA LIMA 202008191076
Acertos: 7,0 de 10,0 22/04/2021
 
 
Acerto: 1,0 / 1,0
Considerando A um conjunto e R uma relação em A, há algumas propriedades a serem respeitadas. No que tange a
propriedade Reflexiva é correto afirmar:
aRb e bRc, então aRc
aRb e bRa, então a=b
 Para todo a ∈ A, aRa
aRb, então bRa 
aRb e bRa, então a≠b
Respondido em 28/04/2021 09:17:33
 
 
Explicação:
Em um conjunto qualquer, podemos dizer que existe relação reflexiva se os subconjuntos deste conjunto
possuírem os mesmos elementos.
 
 
Acerto: 0,0 / 1,0
Com relação ao tema Estrutura de Dados ¿ Grafos, entende se por ¿grau de um nó":
uma entidade, tal como "uma fruta", "uma pessoa".
 uma relação que liga dois nós.
 um conjunto de nós e um conjunto de arestas.
 sequência de nós interligados que liga um nó (origem) a um outro nó (destino).
 
 o número de arestas a ele ligadas.
Respondido em 24/04/2021 12:55:46
 
 
Explicação:
O grau de um grafo indica o número de arestas que conectam um vértice do grafo a outros vértices, ou seja,
número de vizinhos que aquele vértice possui no grafo (que chegam ou partem dele). Para grafos direcionados
são indicados dois tipos de grau, grau de entrada (número de arestas que chegam ao vértice) e grau de saída
(número de arestas que partem do vértice
 
 
Acerto: 0,0 / 1,0
Ao percorrermos uma arvore se visitamos primeiro a subarvore esquerda estamos no percurso em:
 Questão1
a
 Questão2
a
 Questão3
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 2/5
 Pré Ordem
Pós Ordem
Ordem Natural
Ordem Central
 
 Ordem
Respondido em 28/04/2021 09:21:07
 
 
Explicação:
Ordem: Esquerda, Centro, Direita
 
 
Acerto: 0,0 / 1,0
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Q representa 
o estado inicial
 
as transições
 O número de estados
os simbolos de entrada
 o conjunto de estados finais
Respondido em 28/04/2021 09:39:34
 
 
Explicação:
Seguindo a propriedade de um autômato finito que é representado por uma quíntupla (Q, Ʃ, δ, q0, F):
 Q = número de estados = {q0, q1, q2, q3}
 Ʃ = símbolos de entrada = {0,1}
 δ = transições = 
 δ (q0, 0) = q2
 δ (q0, 1) = q1
 δ (q1, 0) = q3
 δ (q1, 1) = q0
 δ (q2, 0) = q0
 δ (q2, 1) = q3
 δ (q3, 0) = não possui = Ø (vazio)
 δ (q3, 1) = q2
 q0 = estado inicial = {q0}
 F = conjunto de estados finais = {q0}
 
 
Acerto: 1,0 / 1,0
Se o estado inicial for também estado final em um autômato finito, então esse autômato
não tem outros estados finais.
não aceita a cadeia vazia.
 aceita a cadeia vazia.
é não determinístico.
 
é determinístico.
Respondido em 28/04/2021 09:22:41
 
 
Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
 
 
Acerto: 1,0 / 1,0
 Questão4
a
 Questão5
a
 Questão6
a
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 3/5
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.
 
 
L(R2) = {w | w termina com b}
Se R3 é uma expressão regular tal que L(R3) = L(R1) ∩ L(R2), então L(R3) é uma linguagem infinita.2). 
 Existe um autômato finito determinístico cuja linguagem é igual a L(R1) ∪ L(R2).
L(R1) = L(r2) 
Respondido em 28/04/2021 09:24:23
 
 
Explicação:
linguagem L(R1) é composta das palavras ou sequências que iniciam com ¿a¿ e a linguagem L(R2) é composta
das palavras ou sequências que iniciam com ¿b¿. Note que a expressão regular (a ∪ b)* gera qualquer
sequência de a´s e b´s. 
Logo, L(R2) não termina com b necessariamente. Sabemos ainda que a união de L(R1) e L(R2) são todas as
palavras que comecem com ¿a¿ ou com ¿b¿, ou seja qualquer palavra sobre o alfabeto, exceto a palavra vazia.
Este AFD pode ser representado com dois estados apenas. Portanto, resta apenas a alternativa C, e como
afirmado anteriormente, um AFD de dois estados reconhece L(R1) ∪ L(R
 
 
Acerto: 1,0 / 1,0
Seja a seguinte linguagem, onde ϵ representa a sentença vazia
SABCD→AB|CD→a|ϵ→b|f→c|g→h|i
Qual o conjunto de terminais que podem começar sentenças derivadas de S?
 {a,b,f,c,g}
 
{a,c,g,h,i}
 
{a,c,g}
{a,b,f,c,g,h,i}
 
{a,b,f}
Respondido em 28/04/2021 09:26:13
 
 
Explicação:
(A) {a,c,g}
(B) {a,b,f,c,g}
(C) {a,b,f,c,g,h,i}
(D) {a,c,g,h,i}
(E) {a,b,f}
Resolução
Na prática, o enunciado solicita o conjunto FIRST de S.
Todos os terminais que iniciam sentenças produzidas pelos não terminais A e C fazem parte do conjunto:
{a,c,g}. Como A produz a cadeia vazia, então devemos também incluir os não terminais que iniciam sentenças
produzidas pelo não terminal B: {b,f}.
Unindo os conjuntos, temos: {a,b,c,f,g}. Portanto, a alternativa correta é a B.
 
 
Acerto: 1,0 / 1,0
Qual das seguintes afirmações é falsa?
 
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
 Questão7
a
 Questão8
a
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 4/5
 O problema da parada é indecidível.
 
 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.
 
 Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
 
Respondido em 28/04/2021 09:27:24
 
 
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.
 
 
Acerto: 1,0 / 1,0
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
 Regras de produção da forma
Conjunto finito de símbolos ou variáveis Não-Terminais
Conjunto finito de símbolos terminais DISJUNTOS
Uma palavra ¿final¿, composta dos símbolos terminais
 
Um símbolo especial escolhido aparte de V denominado inicial
Respondido em 28/04/2021 09:42:24
 
 
Explicação:
V - Conjunto finito de símbolos ou variáveis Não-Terminais, ou seja, são variáveis a serem substituídas por
outras variáveis ou símbolos terminais nos passos de produção das palavras da gramática e nenhum deles
deverá aparecer nas palavras finais da linguagem gerada por ela. 
T -Conjunto finito de símbolos terminais DISJUNTOS , ou seja, que não façam parte de V. Eles são ditos
¿terminais¿ pois são os que farão parte das palavras geradas por essa gramática.
P - Regras de produção da forma: 
S - Um símbolo especial escolhido aparte de V denominado inicial. Este é o símbolo por onde começamos a
substituição das regras de produção.
 
 
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 temimplicaçõ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.
 
 
A asserção I é uma proposição falsa, e a II é uma proposição verdadeira.
 
 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.
 
 Questão9
a
 Questão10
a
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 5/5
A asserção I é uma proposição verdadeira, e a II é uma proposição falsa.
 
As asserções I e II são proposições falsas.
 
Respondido em 28/04/2021 09:30:07
 
 
Explicação:
Uma redução polinomial de um problema NP-completo para um problema pertencente à classe P implica que
P=NP, pois se qualquer problema NPcompleto pode ser resolvido em tempo polinomial, então P=NP, um
problema aberto e fundamental na teoria da computação. Logo, a asserção I está correta.
Por outro lado, quando um problema pertence à classe NP-Completo, o mesmo pode ser reduzido, em tempo
polinomial, a um outro problema da classe NP-Completo. Por isso, ao solucionar um problema em tempo
polinomial, todos podem ser solucionados da mesma forma. 
 
 
 
 
 
 
 
 
 
 
 
javascript:abre_colabore('38403','222994838','4502753122');