Teoria da Computação Teste1-10

Prévia do material em texto

Teoria da Computação
 Questão
Um grafo é:
 Um conjunto de nós interligados por arestas
Um conjunto de arestas interligadas por nós
 
Apenas um conjunto de no.
Um conjunto de nós e de arestas disjuntos
Apenas um conjunto de arestas
Respondido em 13/11/2021 21:49:16
Explicação:
Grafos são um conjunto de vértices (ou nós), interconectados dois a dois por arestas. 
 
 Questão
Quando operamos dois conjuntos e retornamos os elementos existentens no primeiro que não existem no 
segundo temos a operação
INTERSECÇÃO
 DIFERENÇA
UNIÃO
PRODUTO CARTESIANO
 
COMPLEMENTO
Respondido em 13/11/2021 21:49:18
Explicação:
10a
a diferença corresponde a operação
A - B = {x | x A e x B}∈ ∉ 
Ex: Seja A = {0, 1, 2} e B = {2, 3}, então A - B = {0, 1}
 
 Questão
Um grupo de objetos representado como uma unidade é chamado de:
Membro
 Operação
Complemento
 Conjunto
Elemento
Respondido em 13/11/2021 21:49:20
Explicação:
Conforme mostrado na aula 1, conjunto pode ser definido como um agrupamento contendo zero ou mais objetos 
diferentes, chamados de elementos de um conjunto.
 
 Questão
O modelo de computador, com fundamentos lógicos em seu funcionamento onde é feita a análise de computação
combinação e extensões denomina-se
 
GRAFO
AUTOMATOS FINITOS
EXPRESSÕES REGULARES
 LINGUAGENS FORMAIS
 
 MAQUINA DE TURING
Respondido em 13/11/2021 21:49:22
Explicação:
Máquina de Turing é um modelo de computador, com fundamentos lógicos em seu funcionamento. Em máquinas 
de Turing é feita a análise de computação, combinação e extensões das Máquinas de Turing e ao final Máquinas 
de Turing não-deterministas
 
 Questão
Quando operamos dois conjuntos e retornamos todos os elementos existentes tanto no primeiro como no 
segundo conjunto temos a operação
PRODUTO CARTESIANO
 
COMPLEMENTO
INTERSECÇÃO
 UNIÃO
DIFERENÇA
Respondido em 13/11/2021 21:49:24
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ão
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
 aRb, então bRa 
aRb e bRa, então a=b
 Para todo a A, aRa∈
Respondido em 13/11/2021 21:49:26
Explicação:
Em um conjunto qualquer, podemos dizer que existe relação reflexiva se os subconjuntos deste conjunto 
possuírem os mesmos elementos.
 Questão
Com relação ao tema Estrutura de Dados ¿ Grafos, entendese 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.
 o número de arestas a ele ligadas.
 uma relação que liga dois nós.
Respondido em 15/11/2021 14:05:30
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
 
 Questão
É uma noção simples, abstrata e intuitiva, usada para representar a ideia de alguma espécie de relação entre os 
objetos. Graficamente, aparece representado por uma figura com nós ou vértices. Trata-se dos
triângulos.
registros.
 
 grafos.
objetos geométricos.
dados.
Respondido em 15/11/2021 14:05:32
Explicação:
Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou arcos). 
 
 Questão
Pode-se defir o conceito de Grafo bipartido como sendo:
 Grafo onde seus vértices podem ser divididos em dois conjuntos disjuntos, tais que cada aresta ligue 
apenas vértices de grupos diferentes. 
Grafo que tem pesos associados a cada uma de suas arestas.
Grafo não direcionado
Grafo que tem um único vértice e nenhuma aresta
Grafo onde todos os seus vértices têm o mesmo grau
Respondido em 15/11/2021 14:05:36
Explicação:
Um grafo G(V, A) é bipartido quando o seu conjunto de vértices, V, puder ser particionado em dois conjuntos V1 
e V2 tais que toda aresta de G tem uma extremidade em V1 e outra em V2.
 
 Questão
"Um conjunto de pontos com linhas conectando alguns dos pontos, na qual os pontos 
são chamados nós ou vértices , e as linhas são chamadas arestas". Esse conceito é a definição de:
 Grafos
Caminho direcionado.
Algoritmo
Árvore
Arestas
Respondido em 15/11/2021 14:05:40
Explicação:
Conforme visto na aula 2, Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por 
arestas (ou arcos).
 
 Questão
Considerando-se os conceitos básicos de grafos e algoritmos em grafos, assinale a alternativa INCORRETA.
 
 Aresta: conexão entre dois grafos
 
Grafo trivial: Grafo que possui um único vértice e nenhuma aresta
 
 
Vértice: objeto simples que pode ter nome e outros atributos.
 
Grafo: conjunto de vértices e arestas.
 
Grafo completo: grafo não direcionado, no qual todos os pares de vértices são adjacentes.
 
Respondido em 15/11/2021 14:05:44
Explicação:
Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou arcos). 
 
 A aresta portanto interliga nós e não grafos 
 
 Questão
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ó é
 um número associado ao arco, também chamado de peso.
o número de pares ordenados que formam o arco.
 
a posição deste nó em relação ao nó raiz do grafo
a distância entre este nó e um outro nó qualquer do grafo.
 o número de arcos incidentes nesse nó.
Respondido em 15/11/2021 14:05:47
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
 Questão
Complete o seguinte Teorema sobre árvores: "Se todo nó em uma árvore tem uma quantidade finita de filhos e 
todo ramo da árvore tem uma quantidade finita de nós, a árvore propriamente dita tem uma quantidade ........"
finita de ramo
 finita de nós.
infinita de nós
infinita de folha
infinita de ramo
Respondido em 15/11/2021 14:05:59
Explicação:
Como pode ser visto na aula 3 em Percorrendo árvores binárias. 
javascript:abre_colabore('38403','272434496','5001950547');
 
 Questão
Considere que uma arvore binária foi criada a partir da inserção de dados na seguinte ordem 5, 7, 8, 3, 2, 4, 1, 
9
A raiz da subarvore esquerda arvore é o numero 
5
1
 3
7
9
 
Respondido em 15/11/2021 14:06:02
Explicação:
A raiz será o primeiro valor na subarvore esquerda, ou seja menor que a raiz que é o 3
 
 Questão
Entre os diversos tipos de árvores, a árvore enraizada se caracteriza por:
Uma estrutura de vértices que é definida por meio de um conjunto de vértices.
 Um tipo especial de árvore que apresenta 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.
Não apresentar um vértice (raiz) que se distingue dos demais.
Respondido em 15/11/2021 14:06:04
Explicação:
Tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais. É utilizado o termo nó para 
fazer referência aos vértices. 
 
 Questão
Ao percorrermos uma arvore se visitamos primeiro a subarvore esquerda estamos no percurso em:
Pós Ordem
Ordem Central
 
Pré Ordem
Ordem NaturalOrdem
Respondido em 15/11/2021 14:06:08
Explicação:
Ordem: Esquerda, Centro, Direita
 
 Questão
Considere que uma arvore binária foi criada a partir da inserção de dados na seguinte ordem 5, 7, 8, 3, 2, 4, 1, 
9
A raiz da subarvore esquerda arvore é o numero 
9
 
5
1
3
 7
Respondido em 15/11/2021 14:06:12
Explicação:
A raiz será o primeiro valor na subarvore direita, ou seja maior que a raiz que é o 7
 
 Questão
Ao percorrermos uma arvore se visitamos por ultimo o centro estamos no percurso
Ordem
Ordem Natural
Ordem Central
 
 Pós Ordem
Pré Ordem
Respondido em 15/11/2021 14:06:15
Explicação:
Pós-Ordem: Esquerda, Direita, Centro
 Questão
Um autômato finito determinístico , também chamado máquina de estados finita determinística (AFD), é uma 
Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de computação para 
cada cadeia de entrada. É uma de suas propriedades:
 Para todo estado e todo símbolo de entrada sempre há zero ou uma transição possível.
Contém diversos números infinito de estados
Para todo estado e todo símbolo de entrada sempre há zero ou uma ou n transições possíveis.
Há tabelas de transição
Suas transições são incompletas
Respondido em 15/11/2021 14:06:22
Explicação:
Um autômato finito tem um conjunto de estados, alguns dos quais são denominados estados finais. À medida 
que caracteres da string de entrada são lidos, o controle da máquina passa de um estado a outro, segundo um 
conjunto de regras de transição especificadas para o autômato.
 
 Questão
Um automato finito é representado por um quintupla (Q, , δ, q0, F)Ʃ onde representaƩ 
O número de estados
o estado inicial
 
o conjunto de estados finais
as transições
 os simbolos de entrada
Respondido em 15/11/2021 14:06:27
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}
 
 Questão
Uma das formas de representação do autômato finito indeterminístico mais comum é:
Conjunto
Símbolo
 Diagrama
Matriz
Setas
Respondido em 15/11/2021 14:06:29
Explicação:
.
 
 Questão
Quanto aos automatos deterministicos podemos afirmar que:
 Para cada estado e para cada entrada só há zero ou uma transição possível
 
Pode estar em muitos estados ao mesmo tempo.
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis.
Não é representado por uma quíntupla
É 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 15/11/2021 14:06:33
Explicação:
Um autômato finito determinístico é um autômato onde para cada estado e para cada entrada só há zero ou uma
transição possível
 
 Questão
Os movimentos realizado pelos automatos finitos constituem :
O controle
O conjunto de estados
Os dados representados
 O conjunto de transições
O estado final 
 
Respondido em 15/11/2021 14:06:37
Explicação:
Conjunto de transições: movimentos possíveis de um estado para outro
 
 Questão
Um automato finito é representado por um quintupla (Q, , δ, q0, F) onde Q representaƩ 
o estado inicial
 
o conjunto de estados finais
 O número de estados
os simbolos de entrada
as transições
Respondido em 15/11/2021 14:06:49
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}
 Questão
Se o estado inicial for também estado final em um autômato finito, então esse autômato
é não determinístico.
 
não aceita a cadeia vazia.
é determinístico.
não tem outros estados finais.
 aceita a cadeia vazia.
Respondido em 15/11/2021 14:06:58
Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
 
 Questão
Um automato finito é representado por um quintupla (Q, , δ, q0, F) onde q0 representaƩ 
 
 o estado inicial
 
o conjunto de estados finais
O número de estados
as transições
os simbolos de entrada
Respondido em 15/11/2021 14:07:02
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}
 
 Questão
Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem definidas e 
compreendidas. Está é uma característica encontrada nos:
Árvores Binária
Grafos
Autômatos Indeterminados
Autômatos Infinitos
 Autômatos Finitos
Respondido em 15/11/2021 14:07:05
Explicação:
Os Autômatos Finitos são facilmente descritas por expressões simples, chamadas Expressões Regulares.
 
 Questão
Seja um Autômato Finito Não Determinístico (AFN) com 4 estados. Aplicando-se o algoritmo de conversão de um
AFN para um Autômato Finito Determinístico (AFD), em quantos estados, no máximo, resultaria o AFD 
considerando-se os estados inúteis?
 
64
 16
32
8
128
 
Respondido em 15/11/2021 14:07:07
Explicação:
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
 
 Questão
Um automato finito é representado por um quintupla (Q, , δ, q0, F) onde FƩ representa 
 
as transições
O número de estados
os simbolos de entrada
o estado inicial
 
 o conjunto de estados finais
Respondido em 15/11/2021 14:07:11
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}
 
 Questão
A definição formal diz que um autômato finito é uma lista de cinco objetos: conjunto de estados, alfabeto de 
entrada, regras para movimentação, estado inicial, e estados de aceitação. Essa lista de cinco elementos é 
frequentemente chamada:
Array
 quíntupla
Mapeamento
Five elements
Autômato quinto
Respondido em 15/11/2021 14:07:15
Explicação:
Dizemos que um autômato finito é representado por uma quíntupla (Q, , δ, qƩ 0, F), onde Q é o conjunto finito de
estados, é o conjunto finito de símbolos de entrada, δ é a função de transição, q0 é o estado inicial (qƩ 0 Q ∈ o 
estado inicial é apontado por uma seta) e F o conjunto de estados finais ou de aceitação (os estados de aceitação
são apontados por um círculo dentro de outro ou asterisco e um estado inicial também pode ser final).Questão
Uma gramática G é definida por G=({x,y,z},{S,W,X,Y,Z},P,S) na qual os membros de P são
S WZW X|YX x|xXY y|yYZ z|zZ→ → → → →
Qual das expressões regulares abaixo corresponde a esta gramática?
(xx|yy) zz∗ ∗
xx (yy |zz )∗ ∗ ∗
 xx |yy |zz∗ ∗ ∗
 
 (xx |yy )zz∗ ∗ ∗
 xx yy zz∗ ∗ ∗
Respondido em 15/11/2021 14:08:10
Explicação:
Os símbolos não terminais X, Y e Z produzem, respectivamente, xx , yy e zz . Além disso, podemos eliminar W ∗ ∗ ∗
substituindo-o na primeira produção:
SXYZ (X|Y)Z xx∗ yy∗ zz∗→ → → →
Substituindo X, Y e Z na primeira produção, obtemos
Portanto a solução é S (xx∗|yy∗)zz∗→ 
 
 Questão
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(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). 
L(R1) = L(r2) 
Respondido em 15/11/2021 14:08:17
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∪
 
 Questão
Analise as seguintes igualdades de expressões regulares:
I. a =(a )∗ ∗∗
II. (a+b) =(b+a)∗ ∗
III. a +b =(a+b)∗ ∗ ∗
A análise permite concluir que.
somente as igualdades II e III são verdadeiras.
todas as igualdades são verdadeiras.
 somente as igualdades I e II são verdadeiras.
 
somente a igualdade I é verdadeira.
nenhuma das igualdades é verdadeira.
Respondido em 15/11/2021 14:08:28
Explicação:
(A) somente as igualdades I e II são verdadeiras.
(B) somente a igualdade I é verdadeira.
(C) somente as igualdades II e III são verdadeiras.
(D) todas as igualdades são verdadeiras.
(E) nenhuma das igualdades é verdadeira.
Resolução
Nas afirmativas II e III o operador "+" não é o fecho positivo e sim o operador de união. Podemos reescrever as 
afirmativas da seguinte forma:
II. (a|b) =(b|a)∗ ∗
III. a |b =(a|b)∗ ∗ ∗
A afirmativa I está correta (é trivial).
A afirmativa II também está correta (também é trivial, pois o operador de união "|" é comutativo).
A afirmativa III está errada. Enquanto a expressão regular à esquerda reconhece cadeias contendo apenas a's ou
cadeias contendo apenas b's, a expressão regular à direita reconhece qualquer cadeia de a's e b's. Por exemplo, 
a cadeia aab é reconhecida por (a|b) , mas não é reconhecida por a |b .∗ ∗ ∗
Portanto, a alternativa correta é a A.
 
 Questão
Seja o alfabeto ∑ constituído das 23 letras {a, b,c ...,z}. Se A= {legal, ruim} e B= {menino, menina} então o 
resultado de B concatenado A (B.A) será respectivamente:
{menino, menina, ruim, legal}
{legal, ruim, menino, menina}
{meninolegal, meninaruim, meninoruim, meninalegal}
 {meninolegal, meninalegal, meninoruim meninaruim}
{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
Respondido em 15/11/2021 14:08:31
Explicação:
Lembrando que concatenação é uma operação que junta cadeias de um conjunto com cadeias de um outro 
conjunto. 
 
 Questão
Considere as seguintes afirmações sobre autômatos finitos 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 afirmativa correta:
As afirmativas I e II são verdadeiras
As afirmativas I e III são verdadeiras
 
 Apenas a afirmativa III é verdadeira
As afirmativas II e III são falsas
As afirmativas I e III são falsas
Respondido em 15/11/2021 14:08:35
Explicação:
A primeira afirmaçã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 afirmativa 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 afirmativa 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.
 
 Questão
Seja Σ={a,b}. Uma expressão regular denotando a linguagem L = {w Σ tal que toda ocorrência de "a" em w é ∈ ∗
imediatamente seguida de "b"} é:
(ab)∗
 
(a b)∗ ∗
 a b∗
 b+(ab)∗
 (b+ab)∗
Respondido em 15/11/2021 14:08:41
Explicação:
(A) (a b)∗ ∗
(B) (b+ab)∗
(C) a b∗
(D) b+(ab)∗
(E) (ab)∗
As alternativas A e C estão incorretas, pois as expressões regulares reconhecem, por exemplo, a cadeia aab, que
não faz parte da linguagem do enunciado.
A alternativa E também está errada. O problema é que ela não reconhece todas as cadeias da linguagem do 
enunciado. Por exemplo, a cadeia bab faz parte de L, mas não é reconhecida pela ER.
A alternativa D está errada. Entretanto, a ER dessa alternativa é confusa, pois não temos como saber se o 
operador "+" é o fecho positivo ou o operador de união, que é normalmente representado por "|". Felizmente, 
em ambos os casos a alternativa estaria errada.
Portanto, a única alternativa correta é a B.
 Questão
Para gerar o automâto finito mínimo a partir um automâto finito o devemos pelo algoritmo de minimização é 
necessario que:
 Ele seja deterministico
A partir de uma estado existam 0, 1 ou n transições
 
Ele tenha destinos inalcançaveis
A função programa seja parcial
Todos os estados sejam alcançaveis a partir de qualquer outro estado
Respondido em 15/11/2021 14:08:53
Explicação:
Algoritmo de Minimização de Autômatos
PRE-REQUISITOS DO AUTÔMATO A SER MINIMIZADO
a.Deve ser determinístico
b.Todos os estados devem poder ser alcançados a partir do estado inicial (Sem estados inalcançáveis
c.A função programa deve ser total, ou seja, a partir de qualquer estado deve haver transições para todos os 
símbolos do alfabeto
 
 Questão
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,c,g,h,i}
 
{a,c,g}
{a,b,f}
 {a,b,f,c,g}
 
{a,b,f,c,g,h,i}
 
Respondido em 15/11/2021 14:08:56
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.
 
 Questão
Sobre a hierarquia de Chomsky podemos afirmar que: 
 Uma linguagem que não é regular é livre de contexto
 
 Há linguagens que não são nem livres de contexto nem sensíveis ao contexto
 
 As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem
 
Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular
 
 
 As linguagens reconhecidaspor autômatos a pilha são as linguagens regulares
Respondido em 15/11/2021 14:09:00
Explicação:
a - Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular
b- As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem
c - Uma linguagem que não é regular é livre de contexto
d - As linguagens reconhecidas por autômatos a pilha são as linguagens regulares
e - Há linguagens que não são nem livres de contexto nem sensíveis ao contexto
A alternativa A é falsa. Segue o teorema das linguagens recursivamente enumeráveis:
Teorema: Qualquer linguagem gerada por uma gramática irrestrita é recursivamente enumerável .
Uma das consequências desse teorema é que todas as linguagens regulares são recursivamente enumeráveis, 
uma vez que toda gramática regular também é irrestrita.
Toda linguagem livre de contexto também é sensível ao contexto, portanto a alternativa B é falsa.
A alternativa C está errada porque quando uma linguagem não é regular, ela também pode ser sensível ao 
contexto ou irrestrita.
A alternativa D está errada. As linguagens reconhecidas por autômatos a pilha são linguagens livres de contexto. 
Apesar das linguagens regulares também serem livres de contexto e, portanto, também serem reconhecidas por 
um autômato a pilha, a afirmação exclui as linguagens que são puramente livres de contexto.
A alternativa E está correta. Tais linguagens são irrestritas (ou estruturadas em frase).
 
 Questão
Analise as seguintes afirmativas.I. Todo autômato finito não-determinístico pode ser simulado por um autômato 
finito determinístico.
II. Todo autômato finito determinístico pode ser simulado por um autômato finito não-determinístico.
III. Todo autômato finito 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 finito não-determinístico.
V. Todo autômato finito 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 afirmativas I, II, III e IV.
apenas as afirmativas II, III e V.
apenas as afirmativas II e IV.
 apenas as afirmativas I, II, III e V.
 
apenas as afirmativas I, II e IV.
Respondido em 15/11/2021 14:09:04
Explicação:
(A) apenas as afirmativas I, II, III e IV.
(B) apenas as afirmativas II, III e V.
(C) apenas as afirmativas I, II, III e V.
(D) apenas as afirmativas II e IV.
(E) apenas as afirmativas I, II e IV.
Resolução
A única afirmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que 
autômatos finitos reconhecem linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato finito, pois a classe de linguagens 
que esse último reconhece é hierarquicamente inferior.
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
 
 Questão
Analise as seguintes afirmativas.
I. Todo autômato finito não-determinístico pode ser simulado por um autômato finito determinístico.
II. Todo autômato finito determinístico pode ser simulado por um autômato finito não-determinístico.
III. Todo autômato finito 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 finito não-determinístico.
V. Todo autômato finito 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 afirmativas II e IV.
 
apenas as afirmativas II, III e V.
 
apenas as afirmativas I, II, III e IV.
 
apenas as afirmativas I, II e IV.
 apenas as afirmativas I, II, III e V.
 
Respondido em 15/11/2021 14:09:08
Explicação:
(A) apenas as afirmativas I, II, III e IV.
(B) apenas as afirmativas II, III e V.
(C) apenas as afirmativas I, II, III e V.
(D) apenas as afirmativas II e IV.
(E) apenas as afirmativas I, II e IV.
Resolução
A única afirmativa falsa é a IV. Autômatos de pilha reconhecem linguagens livres de contexto, enquanto que 
autômatos finitos reconhecem linguagens regulares.
Portanto, é impossível simular um autômato de pilha utilizando um autômato finito, pois a classe de linguagens 
que esse último reconhece é hierarquicamente inferior.
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha.
Logo, a alternativa correta é a C.
 
 Questão
Seja a linguagem formal L={anb2nc,n≥0}. Analise as seguintes assertivas.
I. L é uma linguagem livre de contexto.
II. A gramática G=({S,X},{a,b,c},{S Xc,X aXbb| },S) gera a linguagem L.→ → ϵ
III. L não pode ser reconhecida por um autômato com pilha.
A análise permite concluir que estão CORRETAS
 
todas as assertivas.
 
 apenas as assertivas I e II.
 
apenas as assertivas II e III.
 
apenas as assertivas I e III.
nenhuma das assertivas.
Respondido em 15/11/2021 14:09:12
Explicação:
(A) apenas as assertivas I e II.
(B) apenas as assertivas I e III.
(C) apenas as assertivas II e III.
(D) todas as assertivas.
(E) nenhuma das assertivas.
Resolução
As afirmativas I e II estão corretas. A gramática G é livre de contexto e produz corretamente a linguagem L.
A produção X aXbb| produz anb2n, isto é, para cada a à esquerda, teremos dois b's à direita. Essa "simetria" → ϵ
não pode ser expressa por uma gramática regular.
Uma vez que a gramática G é livre de contexto, então a linguagem L, produzida por G, é livre de contexto.
A afirmativa III está incorreta, pois como a linguagem L é livre de contexto, então ela é reconhecida por um 
autômato com pilha.
Portanto, a alternativa correta é a A.
 Questão
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?
Substitui todos os 1¿s por 0¿s na fita.
 
Para assim que encontrar um 0.
Substitui todos os 0¿s por 1¿s na fita.
 Anda para a direita até encontrar um 1, substitui por 0 e para. 
Anda para a direita indefinidamente, sem modificar a fita.
Respondido em 15/11/2021 14:09:22
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.
 
 Questão
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações 
lógicas. 
O conjunto de símbolos usados pela máquina de Turing é infinito. 
 Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer 
uma condição de parada. 
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 fita. 
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 fita em cada argumento da função de transição.
 
 
Respondido em 15/11/2021 14:09:25
Explicação:
.
 
 Questão
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 
finita, decidir se o algoritmo termina ou se executará indefinidamente.
Para o problema da parada, 
 não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
 
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çãopolinomial 
que o soluciona, fornecendo respostas aproximadas.
 
existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
 
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução 
exponencial que o soluciona, fornecendo respostas aproximadas.
 
Respondido em 15/11/2021 14:09:28
Explicação:
O problema da parada pode ser definido como:
Seja S o conjunto de todos os pares (A,D), em que A é um algoritmo, e D, dado de 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 afirmam que existe um algoritmo que resolve o 
problema.
As respostas das alternativas D e E não estão corretas, pois afirmam que existe um algoritmo de aproximação e, 
pelo exposto na justificativa da resposta correta, tal algoritmo não existe.
 
 Questão
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.
 
irregulares. 
regulares. 
sensíveis ao contexto. 
Respondido em 15/11/2021 14:09:31
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
 
 Questão
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
O programa
A fita
 A unidade de controle
 
A memoria
O processador
Respondido em 15/11/2021 14:09:34
Explicação:
UNIDADE DE CONTROLE ¿ Contém o estado corrente da máquina, lê ou escreve dados na fita e pode se mover 
para a ¿frente¿(direita) ou para ¿trás¿(esquerda)
 
 Questão
Qual das seguintes afirmações é falsa?
 
 Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
 
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
 O problema da parada é indecidível.
 
 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.
 
Respondido em 15/11/2021 14:09:37
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.
 Questão
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
Uma palavra ¿final¿, composta dos símbolos terminais
 
Conjunto finito de símbolos ou variáveis Não-Terminais
Um símbolo especial escolhido aparte de V denominado inicial
Conjunto finito de símbolos terminais DISJUNTOS
 Regras de produção da forma
Respondido em 15/11/2021 14:10:30
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.
 
 Questão
Considere a gramática G definida pelas regras de produção abaixo, em que os símbolos não-terminais são S, A e 
B, e os símbolos terminais são a e b. 
S -> AB
AB -> AAB
A -> a
B -> b
Com relação a essa gramática, é correto afirmar que
a gramática G gera a cadeia nula.. 
a cadeia aabbb é gerada por essa gramática.
a gramática G é uma gramática livre de contexto.
 é possível encontrar uma gramática regular equivalente a G.
a gramática G é ambígua.
Respondido em 15/11/2021 14:10:35
Explicação:
Quanto ao tipo da gramática, ela não é livre de contexto (alternativa B), pois uma das regras, a segunda, tem 
dois símbolos do lado esquerdo. 
As alternativas C e E estão incorretas porque nem a sentença nula, nem a sentença aabbb têm o formato aa*b 
(note que as sentenças da linguagem têm exatamente um b)
 
 Questão
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:
Pilha
 Gramáticas livres-do-contexto
Expressões regulares
Autômatos infinitos
Autômatos finitos
Respondido em 15/11/2021 14:10:36
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.
 
 Questão
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
III e IV.
 
I.
I e III.
 II.
II e IV.
Respondido em 15/11/2021 14:10:41
Explicação:
 É uma questão de fácil resolução a partir da correta aplicação das regras de derivação da gramática para a 
construção de palavras.
A técnica a ser utilizada para a justificativa de uma alternativa como falsa é a apresentação de um 
contraexemplo de sequência de derivações que demonstre a falsidade.
A afirmativa I deve ser considerada falsa. O contraexemplo é a geração da palavra-vazia a partir do símbolo 
inicial S (nota do autor: essa é uma suposição, já que a questão pode ser considerada mal construída já que não 
informa qual dos símbolos, S, A ou B, é o símbolo inicial).
S => e (aplicação da regra S->e)
A afirmativa II é verdadeira. Considere a seguinte sequência de derivações, na qual W representa uma cadeia de 
símbolos terminais. A derivação demonstra as duas únicas regras que podem ser aplicadas a qualquer momento 
para remover o símbolo terminal B da palavra sendo gerada, de forma que número de zeros consecutivos será 
sempre no máximo dois.
S =>* W0A
 => W00B (Aplicação da regra S->0B é a única que gera zeros seguidos.)
 => W001S (Aplicação da regra B->1S.)
 ou
 => W00 (Aplicação da regra B->e.)
A afirmativa III é trivialmente falsa, já que a palavra-vazia pertence ao conjunto de palavras da linguagem 
geradapela gramática apresentada. Ou seja, a quantidade zero de símbolos uns e zeros torna a afirmativa falsa. 
A seguinte sequência de derivações é o contraexemplo que justifica a afirmativa.
S => e (aplicação da regra S->e)
A afirmativa IV deve ser considerada falsa, pois é possível gerar a palavra 01 (na qual uns aparecem à direita de 
zeros) a partir da seguinte sequência de derivações do contraexemplo.
S => 0A (Aplicação da regra S->0A.)
S => 01S (Aplicação da regra A->1S.)
S => 01 (Aplicação da regra S->e.)
 
 Questão
A gramática dada pelos descritores abaixo é:
G=
N={S,A}
T={0,1} e P é o conjunto de produções
{S 0S 1A 01ε e A 0S 1A 0}→ →
Uma gramática sensível a contexto que não é gramática livre de contexto
Uma gramática livre de contexto que não é gramática regular
Uma gramática do tipo 0 que não é gramática sensível a contexto.
Uma gramática sem categorização possível e que gera a coleção das palíndromas em {0,1} 
exclusivamente de tamanho par.
 
 Uma gramática regular. 
Respondido em 15/11/2021 14:10:47
Explicação:
Pela forma das produções, sabe-se que a gramática é regular já que apresenta produções com cadeia de 
tamanho 1 à esquerda que podem ser substituídas por cadeias exclusivamente do tipo A α onde onde α é →
constituída por um terminal ou por um terminal seguido de um não terminal.
Sabe-se também que existe uma hierarquia onde as gramáticas se incluem de modo que uma G0 inclui as GSC´s
que por sua vez incluem as GLC´s e estas incluem como tipo especial as gramáticas regulares. Assim, se as 
regras satisfazem as condições do tipo mais interior, a opção correta é a letra D
 
 Questão
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o que T significa?
Regras de produção da forma
Uma palavra ¿final¿, composta dos símbolos terminais
 
Conjunto finito de símbolos ou variáveis Não-Terminais
 Conjunto finito de símbolos terminais DISJUNTOS
Um símbolo especial escolhido aparte de V denominado inicial
Respondido em 15/11/2021 14:10:49
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.
 Questão
A área de complexidade de algoritmos abrange a medição da eficiência de um algoritmo frente
à quantidade de operações realizadas até que ele encontre seu resultado final.
A respeito desse contexto, suponha que um arquivo texto contenha o nome de N cidades de determinado estado,
que cada nome de cidade esteja separado do seguinte por um caractere especial de fim de linha e classificado 
em ordem alfabética crescente. Considere um programa que realize a leitura linha a linha desse arquivo, à 
procura de nome de cidade.
Com base nessa descrição, verifica-se que a complexidade desse programa é:
 O(N), em caso de busca sequencial.
O(1), em caso de busca sequencial.
O(N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(log2N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a busca.
O(log2N), em caso de busca binária.
Respondido em 15/11/2021 14:10:59
Explicação:
A análise de complexidade de algoritmos é realizada através da análise assintótica, que utiliza a notação O. 
Existe um arquivo em formato texto e ficamos sabendo que: (a) o tamanho da entrada é definido pelo número 
de cidades N, (b) os nomes estão em ordem alfabética e (c) cada nome de cidade está em uma linha. O 
programa que deve ser analisado procura o nome de uma cidade no arquivo, realizando a leitura linha a linha.
A alternativa A assume que a busca sequencial pode ser realizada em tempo constante (0(1)), ou seja, encontrar
o elemento da primeira posição do arquivo tem o mesmo tempo de execução que encontrar o elemento da 
segunda posição ou mesmo a última (posição N). Como o arquivo é lido linha a linha, claramente para encontrar 
o primeiro elemento será necessário ler apenas a primeira linha;
para o segundo elemento, as duas primeiras linhas; e assim sucessivamente até necessitar realizar a leitura das 
N linhas do arquivo para o último elemento. Desta forma temos um crescimento linear no número de elementos 
e não constante, correspondendo à alternativa B, que é a correta para a questão.
Para a análise da alternativa C, assumimos que não é possível fazer acesso aleatório ao arquivo, pois as linhas 
podem ter tamanho variável e o deslocamento para a linha de posição (N/2) teria de ser realizado linha a linha 
(sequencial) até encontrar N/2 marcadores de final de linha (e desta forma não será possível executar o 
algoritmo em tempo logarítmico). Podemos projetar, ainda, um algoritmo que calcula o ponto médio do arquivo a
partir do seu tamanho em número de bytes e que ¿ajusta¿ para o marcador de final de linha mais próximo. Este 
algoritmo poderia executar em tempo logarítmico se o sistema permitisse acesso aleatório por caracteres, o que 
não é possível, pois o enunciado define que a leitura é realizada linha a linha; logo a alternativa é falsa.
As duas últimas alternativas supõem a transferência dos dados para uma árvore binária, sem especificar qual o 
seu tipo. Em uma árvore binária de pesquisa balanceada, o tempo de busca é O(log2N) e, em uma 
implementação simples de árvore binária, o tempo de busca é O(N), que fazem com que essas alternativas 
pareçam plausíveis. O tempo de construção da árvore balanceada é O(N*log2N), com N operações de leitura ao 
arquivo e, para cada elemento, no mínimo log2N operações para realizar a inserção. Caso a árvore não seja 
balanceada, o custo de inserção de cada elemento é O(N) e o tempo de construção O(N^2). Logo as duas 
últimas alternativas são falsas, pois o tempo total do algoritmo será a soma do tempo de construção mais o 
tempo de busca
 
 Questão
Analise o custo computacional dos algoritmos a seguir, que calculam o valor de um polinômio de grau n, da 
forma: P(x) = an xn+an-1 + xn-1+ ... +a1x + a0, onde os coeficientes são números de ponto flutuante 
armazenados no vetor a[0..n], e o valor de n é maior que zero. Todos os coeficientes podem assumir qualquer 
valor, exceto o coeficiente an que é diferente de zero.
Algoritmo 1:
soma = a[0]
Repita para i = 1 até n
Se a[i] ≠ 0.0 então
potencia = x
Repita para j = 2 até i
potencia = potência * x
Fim repita
soma = soma + a[i] * potencia
 Fim se
Fim repita
Imprima (soma)
Algoritmo 2:
soma = a[n]
Repita para i = n-1 até 0 passo -1
soma = soma * x + a[i]
Fim repita
Imprima (soma)
Com base nos algoritmos 1 e 2, avalie as asserções a seguir e a relação proposta entre elas.
I. Os algoritmos possuem a mesma complexidade assintótica.
PORQUE
II. Para o melhor caso, ambos os algoritmos possuem complexidade O(n).
A respeito dessas asserções, assinale a opção correta.
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 verdadeiras, e a II é uma justificativa correta da I.
 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.
As asserções I e II são proposições falsas.
 
Respondido em 15/11/2021 14:11:03
Explicação:
Observa-se que o algoritmo 1 contêm dois laços, um externo e um interno, e o algoritmo 1 apresenta 1 laço. O 
laço externo do algoritmo 1 e o laço do algoritmo 2 tem a mesma complexidade, mas a existência de 2 laços no 
algoritmo 1 invalida a asserção I. 
O algoritmo 1 não necessariamente executa o laço interno,sendo que, no melhor caso, não executa o laço 
interno vez alguma. Portanto, a asserção II está correta, e a alternativa D indica esta situação. Pode-se verificar 
que a questão não exige que se verifique detalhadamente se os algoritmos realmente calculam o valor do 
polinômio, apenas que se analise a complexidade dos algoritmos,o que se reduz a analisar o possível número de 
iterações dos mes
 
 Questão
Qual das complexidades abaixo é a menor?
O (2n)
O(log n)
O (n2)
 O (n)
O (n3)
Respondido em 15/11/2021 14:11:07
Explicação:
A menor complexidade é a linear
 
 Questão
O problema P versus NP é um problema ainda não resolvido e um dos mais estudados em Computação. Em inhas
gerais, deseja-se saber se todo problema cuja solução pode ser eficientemente verificada por um computador, 
também pode ser eficientemente obtida por um computador. Por ¿eficientemente¿ ou ¿eficiente¿ significa ¿em 
tempo polinomial¿.
A classe dos problemas cujas soluções podem ser eficientemente obtidas por um computador é chamada de 
classe P. Os algoritmos que solucionam os problemas dessa classe têm complexidade de pior caso polinomial no 
tamanho das suas entradas.
Para alguns problemas computacionais, não se conhece solução eficiente, isto é, não se conhece algoritmo 
eficiente para resolvê-los. No entanto, se para uma dada solução de um problema é possível verificá-la 
eficientemente, então o problema é dito estar em NP. Dessa forma, a classe de problemas para os quais suas 
soluções podem ser eficientemente verificadas é chamada de classe NP.
Um problema é dito ser NP-completo se pertence à classe NP e, além disso, se qualquer outro problema na 
classe NP pode ser eficientemente transformado nesse problema. Essa transformação eficiente envolve as 
entradas e saídas dos problemas.
Considerando as noções de complexidade computacional apresentadas acima, analise as afirmações que se 
seguem.
I. Existem problemas na classe P que não estão na classe NP.
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P,
então A está na classe P.
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
IV. Se P é diferente de NP, então existem problemas na classe P que são NP-completos.
É correto apenas o que se afirma em
 IV.
 I e III.
.
 II e III.
 II e IV.
 
 
 I.
Respondido em 15/11/2021 14:11:08
Explicação:
I. Existem problemas na classe P que não estão na classe NP.
Esta asserção é falsa. Qualquer algoritmo de tempo polinomial A que decide uma linguagem L P pode ser ∈
facilmente convertido em um algoritmo de verificação em tempo polinomial A' que apenas ignora o segundo 
argumento (certificado) e simula A. Portanto, temos que P NP.⊆
II. Se o problema A pode ser eficientemente transformado no problema B e B está na classe P, então A está na 
classe P.
Esta asserção é verdadeira. Apenas interprete problema como decisão de uma linguagem. Logo, a afirmação de 
que a linguagem pode ser transformada eficientemente na linguagem B é equivalente a dizer que A é redutível 
em tempo polinomial para B. 
III. Se P = NP, então um problema NP-completo pode ser solucionado eficientemente.
Esta é uma asserção condicional. Não se sabe até hoje se o antecedente é verdadeiro ou falso.
(embora a probabilidade de que seja falsa é grande). Se ela for falsa, então a implicação é trivialmente 
verdadeira. Se ela for verdadeira, então por definição, qualquer problema em P e, portanto em NP pode ser 
solucionado polinomialmente, isto é, de forma eficiente. Desta forma, como qualquer problema NP-completo está
em NP, segue que ele, por estar também em P, teria também uma solução eficiente.
Logo, a asserção é verdadeira.
IV. Se P ≠ NP, então existem problemas na classe P que são NP-completos.
Esta é também uma asserção condicional. Provamos que ela é falsa, mostrando que ao assumirmos o 
antecedente e o consequente, derivamos uma contradição. Da hipótese de que P ≠ NP e levando em conta que P 
 NP (ver alternativa I), segue que P NP. Desta forma, seja LP um problema em P que seja NP-completo. Pela ⊆ ⊂
definição 8 todo problema em NP pode ser reduzido de forma eficiente a LP 
Daí segue, pela alternativa II, que todo problema em NP estaria em P, isto é, que P = NP. Mas isto é uma
contradição com a hipótese de que P ≠ NP. Portanto, esta afirmação é falsa.
Da discussão acima segue que apenas as afirmativas II e III são verdadeiras
 
 Questão
Considere o processo de fabricação de um produto siderúrgico que necessita passar por n tratamentos térmicos e
químicos para ficar pronto. Cada uma das n etapas de tratamento é realizada uma única vez na mesma caldeira. 
Além do custo próprio de cada etapa do tratamento, existe o custo de se passar de uma etapa para a outra, uma
vez que, dependendo da sequência escolhida, pode ser necessário alterar a temperatura da caldeira e limpá-la 
para evitar a reação entre os produtos químicos utilizados. Assuma que o processo de fabricação
inicia e termina com a caldeira limpa. Deseja-se projetar um algoritmo para indicar a sequência de tratamentos 
que possibilite fabricar o produto com o menor custo total. Nesta situação, conclui-se que
 
A utilização do algoritmo de Dijkstra para se determinar o caminho de custo mínimo entre o estado 
inicial e o final soluciona o problema em tempo polinomial.
 
A solução do problema é obtida em tempo de ordem O(nlogn), utilizando um algoritmo ótimo de 
ordenação.
 
O problema se reduz a encontrar a árvore geradora mínima para o conjunto de etapas do processo, 
requerendo tempo de ordem polinomial para ser solucionado.
 
Uma heurística para a solução do problema de coloração de grafos solucionará o problema em 
tempo polinomial.
 
 Qualquer algoritmo conhecido para a solução do problema descrito possui ordem de complexidade 
de tempo não-polinomial, uma vez que o problema do caixeiro viajante se reduz a ele.
 
Respondido em 15/11/2021 14:11:12
Explicação:
Para modelar este problema utilizando grafos se usa um grafo completo com n+1 vértices representando cada 
uma das etapas e a etapa inicial caldeira limpa. 
As arestas contêm pesos que representam o custo de se passar de uma etapa para a outra. Deseja se sair do 
vértice que representa a caldeira limpa passar por todos os vértices uma única vez e retornar ao vértice caldeira 
limpa de forma que o custo seja mínimo. O problema não pode ser resolvido através de uma arvore geradora 
mínima, pois temos que encontrar um ciclo (exclui C). Não podemos aplicar Dijkstra, pois
temos que garantir que todos os vértices sejam visitados (exclui D). O problema de coloração determina 
conjuntos de tarefas e não uma ordem de tarefas (exclui B). Não é suficiente fazer uma ordenação dos valores 
pois isso não garante que os vértices serão todos visitados uma única vez de forma mínima. Se colocarmos todas
as etapas com o mesmo custo como garantir que será encontrado um ciclo que visite todas os vértices.
O problema em questão corresponde ao problema do Caixeiro Viajante ou Ciclo Hamiltoniano, que é NP-
Completo.
 
 Questão
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.
 
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.
 
As asserções I e II são proposições falsas.
 
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativacorreta da I.
 
Respondido em 15/11/2021 14:11:16
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. 
 Questão 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, então bRa 
aRb e bRc, então aRc
aRb e bRa, então a≠b
aRb e bRa, então a=b
 Para todo a A, aRa∈
Respondido em 15/11/2021 14:17:57
Explicação:
Em um conjunto qualquer, podemos dizer que existe relação reflexiva se os subconjuntos deste conjunto 
possuírem os mesmos elementos.
 Questão Acerto: 1,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ó é
 o número de arcos incidentes nesse nó.
a distância entre este nó e um outro nó qualquer do grafo.
 um número associado ao arco, também chamado de peso.
o número de pares ordenados que formam o arco.
 
a posição deste nó em relação ao nó raiz do grafo
Respondido em 15/11/2021 14:19:31
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
 Questão Acerto: 1,0 / 1,0
Entre os diversos tipos de árvores, a árvore enraizada se caracteriza por:
Um grafo acíclico, não orientado e conectado.
Um grafo acíclico, não orientado mas, possivelmente desconectado.
Não apresentar um vértice (raiz) que se distingue dos demais.
Uma estrutura de vértices que é definida por meio de um conjunto de vértices.
 Um tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais
Respondido em 15/11/2021 14:20:40
Explicação:
Tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais. É utilizado o termo 
nó para fazer referência aos vértices. 
 Questão Acerto: 1,0 / 1,0
Um autômato finito determinístico , também chamado máquina de estados finita determinística (AFD), 
é uma Máquina de estados finita que aceita ou rejeita cadeias de símbolos gerando um único ramo de 
computação para cada cadeia de entrada. É uma de suas propriedades:
 Para todo estado e todo símbolo de entrada sempre há zero ou uma transição possível.
Suas transições são incompletas
Contém diversos números infinito de estados
Para todo estado e todo símbolo de entrada sempre há zero ou uma ou n transições 
possíveis.
Há tabelas de transição
Respondido em 15/11/2021 14:22:05
Explicação:
Um autômato finito tem um conjunto de estados, alguns dos quais são denominados estados finais. À 
medida que caracteres da string de entrada são lidos, o controle da máquina passa de um estado a outro, 
segundo um conjunto de regras de transição especificadas para o autômato.
 Questão Acerto: 1,0 / 1,0
Se o estado inicial for também estado final em um autômato finito, então esse autômato
 aceita a cadeia vazia.
é não determinístico.
 
não aceita a cadeia vazia.
não tem outros estados finais.
é determinístico.
Respondido em 15/11/2021 14:25:44
Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
 Questão Acerto: 1,0 / 1,0
Uma gramática G é definida por G=({x,y,z},{S,W,X,Y,Z},P,S) na qual os membros de P são
S WZW X|YX x|xXY y|yYZ z|zZ→ → → → →
Qual das expressões regulares abaixo corresponde a esta gramática?
(xx|yy) zz∗ ∗
 xx |yy |zz∗ ∗ ∗
 
 (xx |yy )zz∗ ∗ ∗
 xx yy zz∗ ∗ ∗
xx (yy |zz )∗ ∗ ∗
Respondido em 15/11/2021 14:27:00
Explicação:
Os símbolos não terminais X, Y e Z produzem, respectivamente, xx , yy e zz . Além disso, podemos ∗ ∗ ∗
eliminar W substituindo-o na primeira produção:
SXYZ (X|Y)Z xx∗ yy∗ zz∗→ → → →
Substituindo X, Y e Z na primeira produção, obtemos
Portanto a solução é S (xx∗|yy∗)zz∗→ 
 Questão Acerto: 1,0 / 1,0
Para gerar o automâto finito mínimo a partir um automâto finito o devemos pelo algoritmo de 
minimização é necessario que:
A partir de uma estado existam 0, 1 ou n transições
 
 Ele seja deterministico
A função programa seja parcial
Ele tenha destinos inalcançaveis
Todos os estados sejam alcançaveis a partir de qualquer outro estado
Respondido em 15/11/2021 14:27:35
Explicação:
Algoritmo de Minimização de Autômatos
PRE-REQUISITOS DO AUTÔMATO A SER MINIMIZADO
a.Deve ser determinístico
b.Todos os estados devem poder ser alcançados a partir do estado inicial (Sem estados inalcançáveis
c.A função programa deve ser total, ou seja, a partir de qualquer estado deve haver transições para todos 
os símbolos do alfabeto
 Questão Acerto: 1,0 / 1,0
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?
Substitui todos os 1¿s por 0¿s na fita.
 
Anda para a direita indefinidamente, sem modificar a fita.
Para assim que encontrar um 0.
 Anda para a direita até encontrar um 1, substitui por 0 e para. 
Substitui todos os 0¿s por 1¿s na fita.
Respondido em 15/11/2021 14:28:42
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.
 Questão Acerto: 0,0 / 1,0
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
 Conjunto finito de símbolos terminais DISJUNTOS
Um símbolo especial escolhido aparte de V denominado inicial
Uma palavra ¿final¿, composta dos símbolos terminais
 
 Regras de produção da forma
Conjunto finito de símbolos ou variáveis Não-Terminais
Respondido em 15/11/2021 14:29:20
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.
 Questão Acerto: 1,0 / 1,0
A área de complexidade de algoritmos abrange a medição da eficiência de um algoritmo frente
à quantidade de operações realizadas até que ele encontre seu resultado final.
A respeito desse contexto, suponha que um arquivo texto contenha o nome de N cidades de 
determinado estado, que cada nome de cidade esteja separado do seguinte por um caractere especial 
de fim de linha e classificado em ordem alfabética crescente. Considere um programa que realize a 
leitura linha a linha desse arquivo, à procura de nome de cidade.
Com base nessa descrição, verifica-se que a complexidade desse programa é:
 O(N), em caso de busca sequencial.
O(log2N), em caso de busca binária.
O(N), em caso de transferência dos nomes para uma árvore binária e, então, realizar a 
busca.
O(1), em caso debusca sequencial.
O(log2N), em caso de transferência dos nomes para uma árvore binária e, então, realizar 
a busca.
Respondido em 15/11/2021 14:29:52
Explicação:
A análise de complexidade de algoritmos é realizada através da análise assintótica, que utiliza a notação 
O. Existe um arquivo em formato texto e ficamos sabendo que: (a) o tamanho da entrada é definido pelo 
número de cidades N, (b) os nomes estão em ordem alfabética e (c) cada nome de cidade está em uma 
linha. O programa que deve ser analisado procura o nome de uma cidade no arquivo, realizando a leitura 
linha a linha.
A alternativa A assume que a busca sequencial pode ser realizada em tempo constante (0(1)), ou seja, 
encontrar o elemento da primeira posição do arquivo tem o mesmo tempo de execução que encontrar o 
elemento da segunda posição ou mesmo a última (posição N). Como o arquivo é lido linha a linha, 
claramente para encontrar o primeiro elemento será necessário ler apenas a primeira linha;
para o segundo elemento, as duas primeiras linhas; e assim sucessivamente até necessitar realizar a 
leitura das N linhas do arquivo para o último elemento. Desta forma temos um crescimento linear no 
número de elementos e não constante, correspondendo à alternativa B, que é a correta para a questão.
Para a análise da alternativa C, assumimos que não é possível fazer acesso aleatório ao arquivo, pois as 
linhas podem ter tamanho variável e o deslocamento para a linha de posição (N/2) teria de ser realizado 
linha a linha (sequencial) até encontrar N/2 marcadores de final de linha (e desta forma não será possível 
executar o algoritmo em tempo logarítmico). Podemos projetar, ainda, um algoritmo que calcula o ponto 
médio do arquivo a partir do seu tamanho em número de bytes e que ¿ajusta¿ para o marcador de final de
linha mais próximo. Este algoritmo poderia executar em tempo logarítmico se o sistema permitisse acesso 
aleatório por caracteres, o que não é possível, pois o enunciado define que a leitura é realizada linha a 
linha; logo a alternativa é falsa.
As duas últimas alternativas supõem a transferência dos dados para uma árvore binária, sem especificar 
qual o seu tipo. Em uma árvore binária de pesquisa balanceada, o tempo de busca é O(log2N) e, em uma 
implementação simples de árvore binária, o tempo de busca é O(N), que fazem com que essas alternativas
pareçam plausíveis. O tempo de construção da árvore balanceada é O(N*log2N), com N operações de 
leitura ao arquivo e, para cada elemento, no mínimo log2N operações para realizar a inserção. Caso a 
árvore não seja balanceada, o custo de inserção de cada elemento é O(N) e o tempo de construção 
O(N^2). Logo as duas últimas alternativas são falsas, pois o tempo total do algoritmo será a soma do 
tempo de construção mais o tempo de busca