Prévia do material em texto
Meus Simulados
Teste seu conhecimento acumulado
Disc.: TEORIA DA COMPUTAÇÃO
Aluno(a): JOSE LUIZ SILVA DOS SANTOS FERRARI 202104538081
Acertos: 9,0 de 10,0 22/02/2023
Acerto: 1,0 / 1,0
Quando operamos dois conjuntos e retornamos todos os elementos existentes tanto no primeiro como no segundo conjunto
temos a operação
INTERSECÇÃO
UNIÃO
PRODUTO CARTESIANO
DIFERENÇA
COMPLEMENTO
Respondido em 22/02/2023 21:58:36
Explicação:
a União corresponde a operação A ∪ B = {x | x ∈ A ou x ∈ B}
Ex: Seja A = {0, 1, 2} e B = {2, 3}, então A ∪ B = {0, 1, 2, 3}
Questão1
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
Acerto: 1,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".
sequência de nós interligados que liga um nó (origem) a um outro nó (destino).
um conjunto de nós e um conjunto de arestas.
uma relação que liga dois nós.
o número de arestas a ele ligadas.
Respondido em 22/02/2023 22:00:20
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: 1,0 / 1,0
Considere que uma árvore binária foi criada a partir da inserção de dados na seguinte ordem, Dados = {5, 7, 8, 3, 2, 4, 1, 9}
A raiz da subárvore direita é o número
5
9
7
1
3
Respondido em 22/02/2023 22:01:10
Explicação:
Questão2
a
Questão3
a
A raiz será o primeiro valor na subárvore direita, ou seja, o primeiro elemento maior que a raiz que é o 7
Acerto: 1,0 / 1,0
Um automato �nito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Ʃ representa
o conjunto de estados �nais
as transições
O número de estados
o estado inicial
os simbolos de entrada
Respondido em 22/02/2023 22:02:03
Explicação:
Seguindo a propriedade de um autômato �nito 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 �nais = {q0}
Acerto: 0,0 / 1,0
Um automato �nito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa
Questão4
a
Questão5
a
os simbolos de entrada
O número de estados
as transições
o estado inicial
o conjunto de estados �nais
Respondido em 22/02/2023 22:05:04
Explicação:
Seguindo a propriedade de um autômato �nito 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 �nais = {q0}
Acerto: 1,0 / 1,0
Considere as seguintes a�rmações sobre autômatos �nitos e expressões regulares:
I A classe de linguagens aceita por um Autômato Finito Determinístico (AFD) não é a mesma que um Autômato Finito Não
Determinístico (AFND).
II Para algumas expressões regulares não é possível construir um AFD.
III A expressão regular (b+ba)+ aceita os "strings" de b's e a's começando com b e não tendo dois a's consecutivos.
Selecione a a�rmativa correta:
As a�rmativas I e III são falsas
Questão6
a
Apenas a a�rmativa III é verdadeira
As a�rmativas I e II são verdadeiras
As a�rmativas II e III são falsas
As a�rmativas I e III são verdadeiras
Respondido em 22/02/2023 22:07:05
Explicação:
A primeira a�rmação é falsa porque AFDs e AFNDs reconhecem a mesma classe de linguagens (linguagens regulares). Além disso,
essas duas classes de autômatos são equivalentes.
A a�rmativa II também é falsa. Toda expressão regular representa uma linguagem regular que, consequentemente, é reconhecida por
um AFD. Logo, é sempre possível construir um AFD para uma expressão regular.
A a�rmativa III está correta. O único problema é a notação utilizada na expressão regular, que causa confusão. A ER pode ser escrita da
seguinte forma: (b|ba)+. Observe que toda cadeia reconhecida pela ER inicia com b e que não é possível ter dois a's consecutivos.
Acerto: 1,0 / 1,0
Analise as seguintes a�rmativas.I. Todo autômato �nito não-determinístico pode ser simulado por um autômato �nito
determinístico.
II. Todo autômato �nito determinístico pode ser simulado por um autômato �nito não-determinístico.
III. Todo autômato �nito não-determinístico pode ser simulado por um autômato de pilha determinístico.
IV. Todo autômato de pilha determinístico pode ser simulado por um autômato �nito não-determinístico.
V. Todo autômato �nito não-determinístico pode ser simulado por uma máquina de Turing determinística.
A análise permite concluir que estão CORRETAS
apenas as a�rmativas I, II, III e V.
apenas as a�rmativas II, III e V.
apenas as a�rmativas II e IV.
apenas as a�rmativas I, II, III e IV.
apenas as a�rmativas I, II e IV.
Respondido em 22/02/2023 22:08:59
Questão7
a
Explicação:
(A) apenas as a�rmativas I, II, III e IV.
(B) apenas as a�rmativas II, III e V.
(C) apenas as a�rmativas I, II, III e V.
(D) apenas as a�rmativas II e IV.
(E) apenas as a�rmativas I, II e IV.
Resolução
A única a�rmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que autômatos �nitos
reconhecem linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato �nito, pois a classe de linguagens que esse último
reconhece é hierarquicamente inferior.
Além disso, autômatos �nitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
Acerto: 1,0 / 1,0
Na máquina de turing o componente que contem o estado corrente da máquina é:
O programa
A memoria
O processador
A unidade de controle
A �ta
Respondido em 22/02/2023 22:10:29
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)
Questão8
a
Acerto: 1,0 / 1,0
Um método mais poderoso de descrever linguagens que podem descrever certas características que têm uma estrutura
recursiva o que as torna úteis em uma variedade de aplicações. O texto refere-se a:
Autômatos �nitos
Pilha
Gramáticas livres-do-contexto
Expressões regulares
Autômatos in�nitos
Respondido em 22/02/2023 22:11:20
Explicação:
Conforme visto na aula 9, o ponto principal das gramáticas sensíveis ao contexto é que suas regras de produção não são independentes
de uma pré-existência de condições da palavra que está sendo reconhecida.
Acerto: 1,0 / 1,0
Qual das complexidades abaixo é a menor?
O (2n)
O (n3)
O (n)
O (n2)
O(log n)
Respondido em 22/02/2023 22:12:01
Explicação:
A menor complexidade é a linear
Questão9
a
Questão10
a