TEORIA DA COMPUTAÇÃO

Prévia do material em texto

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:
Quando operamos dois conjuntos e retornamos os elementos existentens no primeiro que não existem no segundo temos a
operação
Um grupo de objetos representado como uma unidade é chamado de:
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
aRb e bRa, então a=b
aRb e bRa, então a≠b
aRb e bRc, então aRc
aRb, então bRa 
Para todo a ∈ A, aRa
Explicação:
Em um conjunto qualquer, podemos dizer que existe relação reflexiva se os subconjuntos deste conjunto possuírem os mesmos
elementos.
 
2.
UNIÃO
DIFERENÇA
INTERSECÇÃO
COMPLEMENTO
PRODUTO CARTESIANO
 
Explicação:
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}
 
3.
Conjunto
Operação
Membro
Complemento
Elemento
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.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
 
Quando operamos dois conjuntos e retornamos todos os elementos existentes tanto no primeiro como no segundo conjunto
temos a operação
Um grafo é:
 
4.
GRAFO
MAQUINA DE TURING
AUTOMATOS FINITOS
EXPRESSÕES REGULARES
LINGUAGENS FORMAIS
 
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
 
5.
PRODUTO CARTESIANO
 
UNIÃO
COMPLEMENTO
INTERSECÇÃO
DIFERENÇA
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} 
 
6.
Apenas um conjunto de arestas
Um conjunto de nós e de arestas disjuntos
Um conjunto de nós interligados por arestas
Um conjunto de arestas interligadas por nós
 
Apenas um conjunto de no.
Explicação:
Grafos são um conjunto de vértices (ou nós), interconectados dois a dois por arestas. 
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Com relação ao tema Estrutura de Dados ¿ Grafos, entende se por ¿grau de um nó":
É 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
Pode-se defir o conceito de Grafo bipartido como sendo:
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
 uma relação que liga dois nós.
uma entidade, tal como "uma fruta", "uma pessoa".
 o número de arestas a ele ligadas.
 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.
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
 
2.
objetos geométricos.
triângulos.
dados.
registros.
 
grafos.
Explicação:
Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou arcos). 
 
3.
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 um único vértice e nenhuma aresta
Grafo não direcionado
Grafo que tem pesos associados a cada uma de suas arestas.
Grafo onde todos os seus vértices têm o mesmo grau
Explicação:
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
"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:
Considerando-se os conceitos básicos de grafos e algoritmos em grafos, assinale a alternativa INCORRETA.
 
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 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.
 
4.
Caminho direcionado.
Arestas
Algoritmo
Árvore
Grafos
Explicação:
Conforme visto na aula 2, Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou arcos).
 
5.
Aresta: conexão entre dois grafos
 
Vértice: objeto simples que pode ter nome e outros atributos.
 
Grafo completo: grafo não direcionado, no qual todos os pares de vértices são adjacentes.
 
Grafo trivial: Grafo que possui um único vértice e nenhuma aresta
 
 
Grafo: conjunto de vértices e arestas.
 
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 
 
6.
 um número associado ao arco, também chamado de peso.
 o número de arcos incidentes nesse nó.
o número de pares ordenados que formam o arco.
 
a distância entre este nó e um outro nó qualquer do grafo.
a posição deste nó em relação ao nó raiz do grafo
Explicação:
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
Entre os diversos tipos de árvores, a árvore enraizada se caracteriza por:
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 
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 
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
Não apresentar um vértice (raiz) que se distinguedos demais.
Um grafo acíclico, não orientado e conectado.
Uma estrutura de vértices que é definida por meio de um conjunto de vértices.
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
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. 
 
2.
5
1
7
9
 
3
Explicação:
A raiz será o primeiro valor na subarvore direita, ou seja maior que a raiz que é o 7
 
3.
3
9
 
1
5
7
Explicação:
A raiz será o primeiro valor na subarvore esquerda, ou seja menor que a raiz que é o 3
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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 ........"
Ao percorrermos uma arvore se visitamos por ultimo o centro estamos no percurso
Ao percorrermos uma arvore se visitamos primeiro a subarvore esquerda estamos no percurso em:
 
4.
finita de ramo
infinita de nós
infinita de ramo
infinita de folha
finita de nós.
Explicação:
Como pode ser visto na aula 3 em Percorrendo árvores binárias. 
 
5.
Ordem Central
 
Pré Ordem
Pós Ordem
Ordem Natural
Ordem
Explicação:
Pós-Ordem: Esquerda, Direita, Centro
 
6.
Ordem
Pré Ordem
Ordem Central
 
Pós Ordem
Ordem Natural
Explicação:
Ordem: Esquerda, Centro, Direita
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Q representa 
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Ʃ representa 
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
O número de estados
as transições
o conjunto de estados finais
os simbolos de entrada
o estado inicial
 
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}
 
2.
O número de estados
as transições
o conjunto de estados finais
o estado inicial
 
os simbolos de entrada
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}
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Uma das formas de representação do autômato finito indeterminístico mais comum é:
Quanto aos automatos deterministicos podemos afirmar que:
Os movimentos realizado pelos automatos finitos constituem :
Um autômato finito determinístico , também chamado máquina de estados finita determinística (AFD), é uma Máquina de
 
3.
Símbolo
Matriz
Setas
Conjunto
Diagrama
Explicação:
.
 
4.
É um autômato que permite zero, uma ou mais transições a partir de um estado e para um mesmo símbolo de entrada.
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis.
Pode estar em muitos estados ao mesmo tempo.
Não é representado por uma quíntupla
Para cada estado e para cada entrada só há zero ou uma transição possível
 
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
 
5.
O controle
O conjunto de transições
O estado final 
 
Os dados representados
O conjunto de estados
Explicação:
Conjunto de transições: movimentos possíveis de um estado para outro
 
6.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
Há tabelas de transição
Para todo estado e todo símbolo de entrada sempre há zero ou uma ou n transições possíveis.
Contém diversos números infinito de estados
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.
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:
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem definidas e compreendidas. Está é
uma característica encontrada nos:
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
quíntupla
Autômato quinto
Array
Five elements
Mapeamento
Explicação:
Dizemos que um autômato finito é representado por uma quíntupla (Q, Ʃ, δ, q0, 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 (q0 ∈ 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).
 
2.
o estado inicial
 
o conjunto de estados finais
os simbolos de entrada
as transições
O número de estados
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}
 
3.
Árvores Bináriahttps://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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?
 
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa 
 
Grafos
Autômatos Infinitos
Autômatos Finitos
Autômatos Indeterminados
Explicação:
Os Autômatos Finitos são facilmente descritas por expressões simples, chamadas Expressões Regulares.
 
4.
128
 
64
32
16
8
Explicação:
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados
 
5.
as transições
o estado inicial
 
os simbolos de entrada
o conjunto de estados finais
O número de estados
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}
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Se o estado inicial for também estado final em um autômato finito, então esse autômato
 
6.
é não determinístico.
 
aceita a cadeia vazia.
não aceita a cadeia vazia.
não tem outros estados finais.
é determinístico.
Explicação:
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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?
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
 
 
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
(xx∗|yy∗)zz∗
 xx∗yy∗zz∗
xx∗(yy∗|zz∗)
 xx∗|yy∗|zz∗
 
(xx|yy)∗zz∗
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∗ 
 
2.
L(R2) = {w | w termina com b}
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).
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) 
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
 
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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.
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:
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:
3.
somente as igualdades I e II são verdadeiras.
 
somente as igualdades II e III são verdadeiras.
nenhuma das igualdades é verdadeira.
somente a igualdade I é verdadeira.
todas as igualdades são verdadeiras.
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.
 
4.
{legal, ruim, menino, menina}
{meninolegal, meninaruim, meninoruim, meninalegal}
{menino, menina, ruim, legal}
{meninolegal, meninalegal, meninoruim meninaruim}
{legal, ruim, legallegal, legalruim, ruimruim, legallegal}
Explicação:
Lembrando que concatenação é uma operação que junta cadeias de um conjunto com cadeias de um outro conjunto. 
 
5.
As afirmativas II e III são falsas
As afirmativas I e III são verdadeiras
 
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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"} é:
As afirmativas I e III são falsas
Apenas a afirmativa III é verdadeira
As afirmativas I e II são verdadeiras
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.
 
6.
(b+ab)∗
(ab)∗
 
(a∗b)∗
 a∗b
 b+(ab)∗
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.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
 
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?
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
apenas as assertivas I e II.
 
apenas as assertivas I e III.
nenhuma das assertivas.
apenas as assertivas II e III.
 
todas as assertivas.
 
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.
 
2.
{a,c,g}
{a,c,g,h,i}
 
{a,b,f,c,g}
 
{a,b,f}
{a,b,f,c,g,h,i}
 
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.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Sobre a hierarquia de Chomsky podemos afirmar que: 
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
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.
 
3.
 As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem
 
 Há linguagens que não são nem livres de contexto nem sensíveis ao contexto
 
 Uma linguagem que não é regular é livre de contexto
 
Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular
 
 
 As linguagens reconhecidas por autômatos a pilha são as linguagens regulares
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).
 
4.
apenas as afirmativas I, II, III e IV.
apenas as afirmativas II e IV.
apenas as afirmativas I, II e IV.
apenas as afirmativas II, III e V.
 apenas as afirmativas I, II, III e V.
 
Explicação:
(A) apenas as afirmativas I, II, III e IV.
(B) apenas as afirmativas II, III e V.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
Para gerar o automâto finito mínimo a partir um automâto finito o devemos pelo algoritmo de minimização é necessario que:
(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.
 
5.
apenas as afirmativas II e IV.
 
apenas as afirmativas I, II, III e V.
 
apenas as afirmativas I, II, III e IV.
 
apenas as afirmativas I, II e IV.
apenas as afirmativas II, III e V.
 
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.
 
6.
Ele tenha destinos inalcançaveis
A partir de uma estado existam 0, 1 ou n transições
 
Ele seja deterministico
A função programa seja parcial
Todos os estados sejam alcançaveis a partir de qualquer outro estado
Explicação:
https://simulado.estacio.br/bdq_simulados_exercicio.asp#https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
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?
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta.
 
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, 
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
Para assim que encontrar um 0.
Anda para a direita indefinidamente, sem modificar a fita.
Substitui todos os 0¿s por 1¿s na fita.
Substitui todos os 1¿s por 0¿s na fita.
 
Anda para a direita até encontrar um 1, substitui por 0 e para. 
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.
 
2.
Na máquina de Turing, o processamento inclui a sucessiva aplicação da função programada até ocorrer uma condição de
parada. 
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.
 
 
O conjunto de símbolos usados pela máquina de Turing é infinito. 
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. 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com representações lógicas. 
Explicação:
.
 
3.
 não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial que o soluciona,
fornecendo respostas aproximadas.
 
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
Na máquina de turing o componente que contem o estado corrente da máquina é:
 
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ção exponencial que o soluciona,
fornecendo respostas aproximadas.
 
não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado.
 
existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
 
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.
 
4.
irregulares. 
regulares. 
livres do contexto. 
sem restrição.
 
sensíveis ao contexto. 
Explicação:
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES
 
5.
O processador
A unidade de controle
 
O programa
A fita
A memoria
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Qual das seguintes afirmações é falsa?
 
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)
 
6.
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing.
 
 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.
 
 O problema da parada é indecidível.
 
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é ambígua.
 
 Não existe autômato finito determinístico que reconheça alguma linguagem livre de contexto.
 
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.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
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
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:
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
Um símbolo especial escolhido aparte de V denominado inicial
Conjunto finito de símbolos ou variáveis Não-Terminais
Regras de produção da forma
Uma palavra ¿final¿, composta dos símbolos terminais
 
Conjunto finito de símbolos terminais DISJUNTOS
Explicação:
V - Conjunto finito de símbolos ou variáveis Não-Terminais, ou seja, são variáveis a seremsubstituí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.
 
2.
a gramática G gera a cadeia nula.. 
é possível encontrar uma gramática regular equivalente a G.
a gramática G é ambígua.
a cadeia aabbb é gerada por essa gramática.
a gramática G é uma gramática livre de contexto.
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)
 
3.
Pilha
Gramáticas livres-do-contexto
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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}
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
Expressões regulares
Autômatos finitos
Autômatos infinitos
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.
 
4.
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. 
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.
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
 
5.
II.
III e IV.
 
I.
II e IV.
I e III.
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
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o que T significa?
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 gerada pela 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.)
 
6.
Um símbolo especial escolhido aparte de V denominado inicial
Conjunto finito de símbolos terminais DISJUNTOS
Conjunto finito de símbolos ou variáveis Não-Terminais
Uma palavra ¿final¿, composta dos símbolos terminais
 
Regras de produção da forma
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.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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.
 
 
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).
Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões queserá usado na sua AV e AVS.
 
1.
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.
 
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 verdadeiras, e a II é uma justificativa correta da I.
 
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. 
 
2.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
A respeito dessas asserções, assinale a opção correta.
Qual das complexidades abaixo é a menor?
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
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 verdadeira, e a II é uma proposição falsa.
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 falsas.
 
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
 
3.
O (2n)
O (n)
O (n2)
O(log n)
O (n3)
Explicação:
A menor complexidade é a linear
 
4.
 II e IV.
 
 
 I.
 I e III.
.
 II e III.
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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
 
 IV.
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
 
5.
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.
 
Uma heurística para a solução do problema de coloração de grafos solucionará 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.
 
 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.
 
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 sesair 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.
 
https://simulado.estacio.br/bdq_simulados_exercicio.asp#
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 é:
6.
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.
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.
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
https://simulado.estacio.br/bdq_simulados_exercicio.asp#