Teoria da computação estacio exercicios

Prévia do material em texto

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 
 
Um grafo é: 
 
 
Um conjunto de nós e de arestas disjuntos 
 Um conjunto de nós interligados por arestas 
 
Apenas um conjunto de arestas 
 
Um conjunto de arestas interligadas por nós 
 
 
Apenas um conjunto de no. 
Respondido em 20/11/2020 16:18:08 
 
 
Explicação: 
Grafos são um conjunto de vértices (ou nós), interconectados dois a dois por arestas. 
 
2 
 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, então bRa 
 
aRb e bRa, então a=b 
 
aRb e bRa, então a≠b 
 Para todo a ∈ A, aRa 
Respondido em 20/11/2020 16:18:43 
 
 
Explicação: 
Em um conjunto qualquer, podemos dizer que existe relação reflexiva se os subconjuntos deste 
conjunto possuírem os mesmos elementos. 
 
 
 
3 
 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 
 
COMPLEMENTO 
 
PRODUTO CARTESIANO 
 
Respondido em 20/11/2020 16:19:32 
 
 
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} 
 
 
 
4 
 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 
 
 
 
EXPRESSÕES REGULARES 
 
GRAFO 
 MAQUINA DE TURING 
 
LINGUAGENS FORMAIS 
 
 
AUTOMATOS FINITOS 
Respondido em 20/11/2020 16:19:57 
 
 
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 
 Questão 
 
 
Um grupo de objetos representado como uma unidade é chamado de: 
 
 Conjunto 
 
Membro 
 
Elemento 
 
Complemento 
 
Operação 
Respondido em 20/11/2020 16:20:17 
 
 
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. 
 
 
 
6 
 Questão 
 
 
Quando operamos dois conjuntos e retornamos todos os elementos existentes tanto no primeiro 
como no segundo conjunto temos a operação 
 
 
DIFERENÇA 
 
PRODUTO CARTESIANO 
 
 UNIÃO 
 
INTERSECÇÃO 
 
COMPLEMENTO 
Respondido em 20/11/2020 16:20:25 
 
 
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} 
 
 
1 
 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ó é 
 
 o número de arcos incidentes nesse nó. 
 
o número de pares ordenados que formam o arco. 
 
 
a posição deste nó em relação ao nó raiz do grafo 
 
a distância entre este nó e um outro nó qualquer do grafo. 
 
 um número associado ao arco, também chamado de peso. 
Respondido em 20/11/2020 16:20:56 
 
 
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 
 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 
 
 
registros. 
 
 
objetos geométricos. 
 
dados. 
 
triângulos. 
 grafos. 
Respondido em 20/11/2020 16:21:29 
 
 
Explicação: 
Grafo (graph) é um conjunto de vértices (ou nodos), interconectados dois a dois por arestas (ou 
arcos). 
 
 
 
3 
 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 completo: grafo não direcionado, no qual todos os pares de vértices são adjacentes. 
 
 
Grafo: conjunto de vértices e arestas. 
 
Respondido em 20/11/2020 16:22:08 
 
 
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 
 
 
 
4 
 Questão 
 
Com relação ao tema Estrutura de Dados ¿ Grafos, entendese por ¿grau de um nó": 
 
 
 sequência de nós interligados que liga um nó (origem) a um outro nó (destino). 
 
 
 uma relação que liga dois nós. 
 o número de arestas a ele ligadas. 
 
 um conjunto de nós e um conjunto de arestas. 
 
uma entidade, tal como "uma fruta", "uma pessoa". 
Respondido em 20/11/2020 16:25:09 
 
 
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 
 
 
 
5 
 Questão 
 
 
Pode-se defir o conceito de Grafo bipartido como sendo: 
 
 
Grafo que tem pesos associados a cada uma de suas arestas. 
 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 onde todos os seus vértices têm o mesmo grau 
 
Grafo não direcionado 
Respondido em 20/11/2020 16:22:49 
 
 
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. 
 
 
 
6 
 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: 
 
 
Árvore 
 
Caminho direcionado. 
 
Arestas 
 
Algoritmo 
 Grafos 
Respondido em 20/11/2020 16:25:45 
 
 
Explicação: 
Conforme visto na aula 2, Grafo (graph) é um conjunto de vértices (ou nodos), interconectados 
dois a dois por arestas (ou arcos). 
 
1 
 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. 
 
Não apresentar um vértice (raiz) que se distingue dos demais. 
 
Um grafo acíclico, não orientado e conectado. 
 Um tipo especial de árvore que apresenta um vértice (raiz) que se distingue dos demais 
 
Um grafo acíclico, não orientado mas, possivelmente desconectado. 
Respondido em 20/11/2020 16:25:14 
 
 
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 
 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 
 
 3 
 
7 
 
5 
 
9 
 
 
1 
Respondido em 20/11/2020 16:27:40 
 
 
Explicação: 
A raiz será o primeiro valor na subarvore esquerda, ou seja menor que a raiz que é o 3 
 
 
 
3 
 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 nós. 
 
infinita de nós 
 
infinita de folha 
 
finita de ramo 
 
infinita de ramo 
Respondido em 20/11/2020 16:33:57 
 
 
Explicação: 
Como pode ser visto na aula 3 em Percorrendo árvores binárias. 
 
 
 
4 
 Questão 
 
 
Ao percorrermos uma arvore se visitamos primeiro a subarvore esquerda estamos no percurso em: 
 
 
Pós Ordem 
 
Ordem Central 
 
 Ordem 
 
Ordem Natural 
 
Pré Ordem 
Respondido em 20/11/2020 16:34:23 
 
 
Explicação: 
Ordem: Esquerda, Centro, Direita 
 
 
 
5 
 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 
 
 7 
 
9 
 
 3 
 
5 
 
1 
Respondido em 20/11/2020 16:34:39 
 
 
Explicação: 
A raiz será o primeiro valor na subarvore direita, ou seja maior que a raiz que é o 7 
 
 
 
6 
 Questão 
 
 
Ao percorrermos uma arvore se visitamos por ultimo o centro estamos no percurso 
 
 Pós Ordem 
 
Ordem Natural 
 
Ordem 
 
Pré Ordem 
 
Ordem Central 
 
Respondido em 20/11/2020 16:37:28 
 
 
Explicação: 
Pós-Ordem: Esquerda, Direita, Centro 
1 
 Questão 
 
 
Quanto aos automatos deterministicos podemos afirmar que: 
 
 
Não é representado por uma quíntupla 
 
Para todo estado e todo símbolo de entrada sempre há 0 ou 1 ou n transições possíveis. 
 
Pode estar em muitos estados ao mesmo tempo. 
 Para cada estado e para cada entrada só há zero ou uma transição possível 
 
 
É 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 20/11/2020 16:38:18 
 
 
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 
 
 
 
2 
 Questão 
 
 
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Ʃ representa 
 
 
O número de estados 
 
as transições 
 
o conjunto de estados finais 
 os simbolos de entrada 
 
o estado inicial 
 
Respondido em 20/11/2020 16:36:32 
 
 
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 
 Questão 
 
 
Uma das formas de representação do autômato finito indeterminístico mais comum é: 
 
 
Matriz 
 
Símbolo 
 
Setas 
 Diagrama 
 
Conjunto 
Respondido em 20/11/2020 16:39:28 
 
 
Explicação: 
. 
 
 
 
4 
 Questão 
 
 
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde Q representa 
 
 
o estado inicial 
 
 O número de estados 
 
os simbolos de entrada 
 
o conjunto de estados finais 
 
as transições 
Respondido em 20/11/2020 16:39: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} 
 
 
 
5 
 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 ou n transições 
possíveis. 
 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 
 
Contém diversos números infinito de estados 
Respondido em 20/11/2020 16:38:06 
 
 
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. 
 
 
 
6 
 Questão 
 
 
Os movimentos realizado pelos automatos finitos constituem : 
 
 
Os dados representados 
 
O conjunto de estados 
 
O controle 
 O conjunto de transições 
 
O estado final 
 
Respondido em 20/11/2020 16:38:31 
 
 
Explicação: 
Conjunto de transições: movimentos possíveis de um estado para outro 
 
 
1 
 Questão 
 
 
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde q0 representa 
 
 
 
O número de estados 
 
o conjunto de estados finais 
 
os simbolos de entrada 
 o estado inicial 
 
 
as transições 
Respondido em 20/11/2020 16:41:29 
 
 
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 
 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 tem outros estados finais. 
 
não aceita a cadeia vazia. 
 aceita a cadeia vazia. 
 
é determinístico. 
Respondido em 20/11/2020 16:39:13 
 
 
Explicação: 
Quando o estado inicial também é final num AF, então ele aceita a cadeia vazia. 
 
 
 
3 
 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? 
 
 
 
128 
 
 
32 
 
64 
 
8 
 16 
Respondido em 20/11/2020 16:42:21 
 
 
Explicação: 
 
O cálculo é simples. Basta calcular 2 elevado ao número de estados do AFN: portanto 16 estados 
 
 
 
4 
 Questão 
 
 
Constituem um conjunto de linguagens decidíveis bastante simples e com propriedades bem 
definidas e compreendidas. Está é uma característica encontrada nos: 
 
 Autômatos Finitos 
 
Árvores Binária 
 
Autômatos Indeterminados 
 
Autômatos Infinitos 
 
GrafosRespondido em 20/11/2020 16:40:26 
 
 
Explicação: 
Os Autômatos Finitos são facilmente descritas por expressões simples, chamadas Expressões 
Regulares. 
 
 
 
5 
 Questão 
 
 
Um automato finito é representado por um quintupla (Q, Ʃ, δ, q0, F) onde F representa 
 
 
 o conjunto de estados finais 
 
o estado inicial 
 
 
os simbolos de entrada 
 
as transições 
 
O número de estados 
Respondido em 20/11/2020 16:43:18 
 
 
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} 
 
 
 
6 
 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: 
 
 quíntupla 
 
Mapeamento 
 
Array 
 
Autômato quinto 
 
Five elements 
Respondido em 20/11/2020 16:40:52 
 
 
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). 
 
 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 
 
 
 
 
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) 
 
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} 
Respondido em 20/11/2020 16:45:25 
 
 
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 
 
 
 
2 
 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"} é: 
 
 
 b+(ab)∗ 
 (b+ab)∗ 
 
(a∗b)∗ 
 
 a∗b 
 
(ab)∗ 
 
Respondido em 20/11/2020 16:46:21 
 
 
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. 
 
 
 
3 
 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 20/11/2020 16:46:25 
 
 
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∗ 
 
 
 
4 
 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 II e III são falsas 
 
As afirmativas I e III são falsas 
 
As afirmativas I e III são verdadeiras 
 
 Apenas a afirmativa III é verdadeira 
 
As afirmativas I e II são verdadeiras 
Respondido em 20/11/2020 16:48:01 
 
 
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. 
 
 
 
5 
 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. 
 
 
todas as igualdades são verdadeiras. 
 somente as igualdades I e II são verdadeiras. 
 
 
nenhuma das igualdades é verdadeira. 
 
somente as igualdades II e III são verdadeiras. 
 
somente a igualdade I é verdadeira. 
Respondido em 20/11/2020 16:49:08 
 
 
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. 
 
 
 
6 
 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: 
 
 
{legal, ruim, legallegal, legalruim, 
ruimruim, legallegal} 
 
{meninolegal, meninaruim, meninoruim, 
meninalegal} 
 
{menino, menina, ruim, legal} 
 {meninolegal, meninalegal, meninoruim 
meninaruim} 
 
{legal, ruim,menino, menina} 
Respondido em 20/11/2020 16:50:43 
 
 
Explicação: 
Lembrando que concatenação é uma operação que junta cadeias de um conjunto com cadeias de 
um outro conjunto. 
1 
 Questão 
 
 
Sobre a hierarquia de Chomsky podemos afirmar que: 
 
 
 Uma linguagem que não é regular é livre de contexto 
 
 
Uma linguagem que é recursivamente enumerável não pode ser uma linguagem regular 
 
 
 Há linguagens que não são nem livres de contexto nem sensíveis ao contexto 
 
 
 As linguagens reconhecidas por autômatos a pilha são as linguagens regulares 
 
 As linguagens livres de contexto e as linguagens sensíveis ao contexto se excluem 
 
Respondido em 20/11/2020 17:25:25 
 
 
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). 
 
 
 
2 
 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,b,f,c,g,h,i} 
 
 
{a,c,g} 
 
{a,b,f} 
 {a,b,f,c,g} 
 
 
{a,c,g,h,i} 
 
Respondido em 20/11/2020 17:26:59 
 
 
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. 
 
 
 
3 
 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, III e V. 
 
 
apenas as afirmativas I, II, III e IV. 
 
 
apenas as afirmativas I, II e IV. 
 
apenas as afirmativas II e IV. 
 
 apenas as afirmativas I, II, III e V. 
 
Respondido em 20/11/2020 17:27:55 
 
 
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. 
 
 
 
4 
 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 
 
Todos os estados sejam alcançaveis a partir de qualquer outro estado 
 
A função programa seja parcial 
 
A partir de uma estado existam 0, 1 ou n transições 
 
 
Ele tenha destinos inalcançaveis 
Respondido em 20/11/2020 17:30:56 
 
 
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 
 
 
 
5 
 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 
 
 
 
apenas as assertivas II e III. 
 
 apenas as assertivas I e II. 
 
 
todas as assertivas. 
 
 
nenhuma das assertivas. 
 
apenas as assertivas I e III. 
Respondido em 20/11/2020 17:28:42 
 
 
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. 
 
 
 
6 
 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 e 
IV. 
 apenas as afirmativas I, II, 
III e V. 
 
 
apenas as afirmativas I, II, 
III e IV. 
 
apenas as afirmativas II e 
IV. 
 
apenas as afirmativas II, III 
e V. 
Respondido em 20/11/2020 17:32:19 
 
 
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 é hierarquicamenteinferior. 
Além disso, autômatos finitos não possuem memória auxiliar para simular a pilha. 
Logo, a alternativa correta é a C. 
 Questão 
 
No que concerne a utilização e o processamento de máquina de Turing, assinale a opção correta. 
 
 
 
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. 
 
 
 
As saídas podem ser apenas binárias, pois as referidas máquinas trabalham com 
representações lógicas. 
 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. 
 
O conjunto de símbolos usados pela máquina de Turing é infinito. 
Respondido em 20/11/2020 17:32:56 
 
 
Explicação: 
. 
 
 
 
2 
 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 exato, mas existe algoritmo de aproximação de tempo de execução 
exponencial que o soluciona, fornecendo respostas aproximadas. 
 
 
existe algoritmo exato de tempo de execução polinomial para solucioná-lo. 
 
 
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 
polinomial que o soluciona, fornecendo respostas aproximadas. 
 
 não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado. 
 
Respondido em 20/11/2020 17:33:42 
 
 
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. 
 
 
 
3 
 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? 
 
 Anda para a direita até encontrar um 1, substitui por 0 e para. 
 
Substitui todos os 1¿s por 0¿s na fita. 
 
 
Anda para a direita indefinidamente, sem modificar a fita. 
 
Substitui todos os 0¿s por 1¿s na fita. 
 
Para assim que encontrar um 0. 
Respondido em 20/11/2020 17:34:54 
 
 
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. 
 
 
 
4 
 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 
 
 
sensíveis ao contexto. 
 
regulares. 
 sem restrição. 
 
 
livres do contexto. 
 
irregulares. 
Respondido em 20/11/2020 17:32:46 
 
 
Explicação: 
A MAQUINA DE TURING CORRESPONDE A GRAMATICAS SEM RESTRIÇÕES 
 
 
 
5 
 Questão 
 
 
Na máquina de turing o componente que contem o estado corrente da máquina é: 
 
 
 
A fita 
 A unidade de controle 
 
 
A memoria 
 
O programa 
 
O processador 
Respondido em 20/11/2020 17:33:49 
 
 
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 
 Questão 
 
 
Qual das seguintes afirmações é falsa? 
 
 
 
 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. 
 
 Não existe autômato finito determinístico que reconheça alguma linguagem livre de 
contexto. 
 
 
Um autômato com duas pilhas pode ser simulado por uma máquina de Turing. 
 
 
 
 Não existe algoritmo que determina quando uma gramática livre de contexto arbitrária é 
ambígua. 
 
Respondido em 20/11/2020 17:33:26 
 
 
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 
 
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.. 
 é possível encontrar uma gramática regular equivalente a G. 
 
a gramática G é uma gramática livre de contexto. 
 
a cadeia aabbb é gerada por essa gramática. 
 
a gramática G é ambígua. 
Respondido em 20/11/2020 17:34:56 
 
 
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) 
 
 
 
2 
 Questão 
 
 
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o que T significa? 
 
 
Uma palavra ¿final¿, composta dos símbolos terminais 
 
 Conjunto finito de símbolos terminais DISJUNTOS 
 
Conjunto finito de símbolos ou variáveis Não-Terminais 
 
Um símbolo especial escolhido aparte de V denominado inicial 
 
Regras de produção da forma 
Respondido em 20/11/2020 17:37:48 
 
 
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ímbolosterminais 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. 
 
 
 
3 
 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: 
 
 
Autômatos finitos 
 Gramáticas livres-do-contexto 
 
Expressões regulares 
 
Autômatos infinitos 
 
Pilha 
Respondido em 20/11/2020 17:38:15 
 
 
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 
 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 
 
 
I e III. 
 
I. 
 II. 
 
III e IV. 
 
 
II e IV. 
Respondido em 20/11/2020 17:40:07 
 
 
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 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.) 
 
 
 
5 
 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 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 do tipo 0 que não é gramática sensível a contexto. 
 
Uma gramática livre de contexto que não é gramática regular 
Respondido em 20/11/2020 17:40:25 
 
 
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 
 
 
 
6 
 Questão 
 
 
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa? 
 
 
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 
 
Um símbolo especial escolhido 
aparte de V denominado inicial 
 
Conjunto finito de símbolos 
terminais DISJUNTOS 
Respondido em 20/11/2020 17:40:50 
 
 
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 
 
 
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 20/11/2020 17:43:18 
 
 
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 problemaB 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 
 
 
 
2 
 Questão 
 
 
Qual das complexidades abaixo é a menor? 
 
 
O(log n) 
 
O (n3) 
 
O (n2) 
 
O (2n) 
 O (n) 
Respondido em 20/11/2020 17:46:15 
 
 
Explicação: 
A menor complexidade é a linear 
 
 
 
3 
 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. 
 
 
 
 
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. 
 
 
 
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. 
 
 
Respondido em 20/11/2020 17:44:14 
 
 
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. 
 
 
 
4 
 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 
 
 
 
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. 
 
 
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. 
 
 
Uma heurística para a solução do problema de coloração de grafos solucionará o problema 
em tempo polinomial. 
 
Respondido em 20/11/2020 17:50:58 
 
 
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. 
 
 
 
5 
 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(1), em caso de busca sequencial. 
 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(log2N), em caso de transferência dos nomes para uma árvore binária e, então, 
realizar a busca. 
Respondido em 20/11/2020 17:52:09 
 
 
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; 
parao 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 
 
 
 
6 
 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. 
 
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 verdadeiras, e a II é uma justificativa correta da I. 
 
As asserções I e II são proposições falsas. 
 
Respondido em 20/11/2020 17:50:38 
 
 
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