Prévia do material em texto

31/10/2022 10:54 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/1
Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo é quadrático, quanto tempo em segundos ele
gastará, aproximadamente, no mesmo computador, se a entrada tiver tamanho 100?
( )
Q ×Σ→ (Q × Σ × {L, R, H})
Q ×Σ→ (Q × {L, R, H})
Q × Γ → (Q × Σ × {H})
Data Resp.: 10/10/2022 08:06:34
Explicação:
A função de transição de estados para MT é definida como um produto cartesiano de Q × Γ, onde Γ é alfabeto da fita, levando em uma
imagem definida por outro produto cartesiano de Q × Γ multiplicado pelas ações da máquina em seguir para a esquerda, direita ou parar
{L, R, H}.
 
10.
100.
20.
500.
40.
10.
Data Resp.: 10/10/2022 08:06:38
Explicação:
Como o algoritmo é quadrático, podemos fazer a seguinte aproximação para o tempo de execução: T(n)=cn2, onde c é uma constante a
ser determinada. Sabe-se que T(50)=10, logo c*502 = 10 segundos, então 2500c=10 e determinamos c=1/250. A expressão de
complexidade de tempo para esse algoritmo é T(n)= (1/250) * n2. Logo, T(100) = (1/250)*1002.
T(100) = 10000/250 = 40.
 Não Respondida Não Gravada Gravada
Exercício inciado em 09/10/2022 11:42:27. 
31/10/2022 10:53 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/1
A diferença entre autômatos finitos e autômatos de pilha está na:
Alguns tipos de símbolos e produções aumentam o número de etapas na geração de uma linguagem a partir de
uma GLC. Nesse sentido, símbolos inúteis em uma Gramática Livre de Contexto são:
Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto finito de estados, Σ é o
conjunto finito de alfabetos de entrada, Γ é o símbolo de fita permitido, L significa esquerda, R significa direita e H
significa parada).
 
 
 
 
03493LINGUAGENS LIVRES DE CONTEXTO
 
7.
Cabeça de leitura.
Fita de entrada.
Pilha.
Direção do movimento da cabeça de leitura.
Controle finito.
Data Resp.: 10/10/2022 08:06:29
 
Explicação:
Gabarito: Pilha.
Justificativa: Os autômatos de Pilha são o formato de máquina de autômatos finitos para linguagens livres de
contexto. É um autômato finito com a anexação de uma quantidade auxiliar de armazenamento chamada de
pilha. A pilha é o componente do PDA que o diferencia dos autômatos finitos.
 
 
 
 
8.
Cadeia nula.
Símbolos não terminais.
Produções nulas.
Alfabetos nulos.
Símbolos não geradores e símbolos não alcançáveis.
Data Resp.: 10/10/2022 08:06:31
 
Explicação:
Gabarito: Símbolos não geradores e símbolos não alcançáveis.
Justificativa: Os dois tipos de símbolos inúteis incluem os símbolos não geradores, aqueles símbolos que não
produzem nenhuma cadeia terminal, e os símbolos não alcançáveis, aqueles símbolos que não podem ser
alcançados a qualquer momento a partir do símbolo inicial. Toda linguagem livre de contexto pode ser gerada
por uma gramática livre de contexto em que não há símbolos inacessíveis ou inúteis.
 
 
 
 
 
 
03494COMPUTABILIDADE E A MÁQUINA DE TURING
 
9.
Q × Γ → (Q × Γ × {L, R, H})
Q × Γ → (Q × Σ)
Q ×Σ→ (Q × Σ × {L, R, H})
Q ×Σ→ (Q × {L, R, H})
Q × Γ → (Q × Σ × {H})
Data Resp.: 10/10/2022 08:06:34
 
Explicação:
A função de transição de estados para MT é definida como um produto cartesiano de Q × Γ, onde Γ é alfabeto da
fita, levando em uma imagem definida por outro produto cartesiano de Q × Γ multiplicado pelas ações da
máquina em seguir para a esquerda, direita ou parar {L, R, H}.
31/10/2022 10:53 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/1
Vamos considerar que em uma classe 32 alunos gostam de Geografia e 40 de História. Sabendo que a classe
possui 60 alunos, qual o número de alunos que gostam de Geografia e de História?
Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta?
(POSCOMP / 2008 - adaptada) 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
 
03492LINGUAGENS REGULARES
 
4.
20
36
No mínimo 12
No máximo 12
32
Data Resp.: 10/10/2022 08:06:20
 
Explicação:
Gabarito: No mínimo 12
Justificativa: O conjunto universo tem 60 alunos. O conjunto dos que gostam de geografia tem 32 e o
conjunto dos que gostam de história tem 40. Logo, a intersecção de ambos tem, pelo menos, 12 alunos que
gostam de ambas as disciplinas.
 
 
 
 
5.
S U ∅ = ∅
S ∩ ∅ = S
S U ∅ = S - ∅ = ∅
S - ∅ = ∅
S U ∅ = S - ∅ = S
Data Resp.: 10/10/2022 08:06:23
 
Explicação:
Gabarito: S U ∅ = S - ∅ = S
Justificativa: A união de qualquer conjunto com o conjunto vazio é igual ao próprio conjunto, bem como a
diferença de um conjunto com o conjunto vazio é o próprio conjunto. Assim, a única alternativa correta é S U ∅
= S - ∅ = S.
 
 
 
 
6.
somente a igualdade II é verdadeira.
somente a igualdade III é verdadeira.
somente as igualdades II e III são verdadeiras.
somente a igualdade I é verdadeira.
somente as igualdades I e II são verdadeiras.
Data Resp.: 10/10/2022 08:06:26
 
Explicação:
Gabarito: somente as igualdades I e II são verdadeiras.
Justificativa: a* + b* significa qualquer combinação de 'a' ou qualquer combinação de 'b', ou seja, as cadeias
são formadas apenas por 'a' ou por 'b'. (a + b)* consiste em qualquer combinação de 'a' e 'b', ou seja, as
cadeias podem conter os símbolos 'a' e 'b' em sua formação, logo a alternativa III é falsa. A alternativa II é
verdadeira porque segundo o fecho de Kleene podemos considerar Σ = {a, b} e Σ* definido como o conjunto de
todas as cadeias, incluindo a cadeia nula, portanto as linguagens são iguais e geradas por expressões
equivalentes. A alternativa I é, claramente, verdadeira, bastando retirar os parênteses da expressão à direita.
31/10/2022 10:52 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/1
BIO-RIO - 2014 - ETAM - Curso de Formação de Técnicos - 2º Semestre
Dados três conjuntos, A = {1,2,3}, B = {4,5} e C = {1,2,4}, observe os pares ordenados apresentados
graficamente na figura abaixo.
 
 
Esses pares correspondem, graficamente, a:
Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é:
Câmara Municipal de Marabá- Engenheiro Civil - FADESP-2021
A função exponencial y = ax+1 é tal que a imagem de 2 é 27. A imagem de 4 será:
 
03491CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
 
1.
(A U C) X B
B X (A ∩ C)
B X (A U C)
(A ∩ C) X B
C X (A U B)
Data Resp.: 10/10/2022 08:05:58
 
Explicação:
A fim de que o produto cartesiano de B com qualquer outro conjunto fosse representado, os pares ordenados
devem, necessariamente, iniciar com os elementos do conjunto B = {4, 5}. Como os pares da figura começam
com os elementos 1 e 2, as alternativas a e d estão incorretas. A alternativa ¿e¿ nos obrigaria a ter um par
ordenado começando com elemento 4. A intersecção dos conjuntos A e C contém os elementos comuns {1, 2},
uma vez que 3 não está contido em C. O produto cartesiano desse conjunto intersecção com o conjunto B é:
{(1, 4); (1, 5); (2, 4); (2, 5)}
 
 
 
 
2.
5
64
16
32
10
Data Resp.: 10/10/2022 08:06:09
 
Explicação:
Como sabemos, o número de subconjuntos de um conjunto com n elementos é igual a 2n. Assim, o número de
subcadeias de uma cadeia de tamanho 5 será igual a 25 = 32
 
 
 
 
3.
64
81
729
256
243
Data Resp : 10/10/2022 08:06:17