Simulado W

Prévia do material em texto

A análise sintática é usualmente implementada a partir de uma gramática: 
 
 
 
 Livre de contexto 
 
Sensível ao contexto 
 
Regular 
 
Irrestrita 
 
Com estrutura de frase 
Respondido em 07/10/2022 20:14:12 
 
Explicação: 
As gramáticas regulares são utilizadas para a análise léxica em compiladores de linguagens de 
programação. A parte gramatical da linguagem é verificada por meio de árvores de derivação geradas a 
partir de gramáticas livres de contexto. 
 
 
 
 Questão Acerto: 0,0 / 1,0 
 
 
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett 
Learning, 2016. 
 
(a, b)+ significa 
 
 
 
 Qualquer combinação de a, b excluindo nulo 
 Qualquer combinação de a, b, mas 'b' virá primeiro 
 
λ 
 
Qualquer combinação de a, b incluindo nulo 
 
Qualquer combinação de a, b, mas 'a' virá primeiro 
Respondido em 07/10/2022 20:40:55 
 
Explicação: 
Utilizando o fecho de Kleene, sabemos que a expressão (a, b)+ gera qualquer combinação de cadeias 
compostas pelos símbolos a e b e, necessariamente, não inclui a cadeia nula λ. Neste caso, a ordem em 
que aparecem os símbolos nas cadeias não requer que "a" venha antes de "b". Se isso fosse necessário 
4a 
 
5a 
 
6a 
 
Σ={a,b} L={ω|ω∈Σ∗e on°de a's emωé par} 7a 
 
8a 
 
9a 
 
10a 
 
2a 
 
3a 
 
escreveríamos (ab)+ 
 
 
 
 Questão Acerto: 1,0 / 1,0 
 
 
Sejam os conjuntos A com 2 elementos, B com 4 elementos, C com 5 elementos, então: 
 
 
 
 
(A ∪ B) ∪ C tem no máximo 2 elementos 
 
A ∪ C tem no máximo 5 elementos 
 
A ∩ B tem no máximo 1 elemento 
 
A ∩ ∅ tem 3 elementos pelo menos 
 (A ∩ B) ∩ C tem no máximo 2 elementos 
Respondido em 07/10/2022 20:15:53 
 
Explicação: 
A intersecção de A com B tem no máximo dois elementos, uma vez que o conjunto A só tem dois 
elementos. Essa intersecção pode ter zero, um ou dois elementos. Isto pode ser visto desenhando um 
diagrama de Venn. A U B terá seis elementos e A U C terá sete elementos. Como C tem 5 elementos, mas 
a intersecção de A com B tem, no máximo dois elementos, então (A ∩ B) ∩ C tem, no máximo 2 
elementos. 
 
 
 
 Questão Acerto: 1,0 / 1,0 
 
 
(POSCOMP / 2016) O autômato finito exposto abaixo representa qual expressão regular? 
 
 
 
 
 
a*b (d* + cb) 
 a*b(c + da*b)* 
 
(bb + d)* (aa + c)* 
 
ab*(da* + cb)* 
 
a*c* (b +d)* 
Respondido em 07/10/2022 20:17:50 
 
Explicação: 
Gabarito: a*b(c + da*b)* 
Justificativa: Esse AF reconhece a*b, uma vez que essa cadeia leva a um estado final. Na sequência deve 
reconhecer qualquer número de entradas de 'c' e deixar o estado quando receber uma entrada 'd'. 
Permanecer nesse primeiro estado enquanto entrar 'a' e voltar ao estado final quando entrar um 'b'. Essa 
parte implica reconhecer c*+ da*b. Ocorre que para reconhecer apenas a cadeia a*b essa segunda parte 
tem que ser nula, daí a necessidade de se acrescentar um fecho de kleene na segunda expressão, 
resultando em: a*b(c + da*b)*. 
 
 
 
 Questão Acerto: 0,0 / 1,0 
 
 
A expressão regular que permite reconhecer a digitação correta de CEP no Brasil no modelo ddddd-ddd é: 
 
 
 
 
^\\d{5,1}\\-\\d{3,1}$ 
 
^\\d{5,5}\\-\\d{3,1}$ 
 ^\\d{3,5}\\-\\d{5,3}$ 
 ^\\d{5,5}\\-\\d{3,3}$ 
 
^\\d{3,3}\\-\\d{5,5}$ 
Respondido em 07/10/2022 20:41:33 
 
Explicação: 
Gabarito: ^\\d{5,5}\\-\\d{3,3}$ 
Justificativa: O padrão de CEP no Brasil é composto de 5 dígitos numéricos separados por um traço e mais 
três dígitos. A única alternativa que satisfaz esse padrão é a alternativa "^\\d{5,5}\\-\\d{3,3}$" 
 
 
 
 Questão Acerto: 1,0 / 1,0 
 
 
(POSCOMP / 2009 - adaptada) Seja o alfabeto Σ={a,b} e a linguagem regular L={ω|ω∈Σ∗e on°de a's emωé 
par}. Qual das expressões regulares abaixo gera essa linguagem? 
 
 
 
 
( a | b )* 
 
( ( a )* | b* )* 
 
( b* | ( a )* | b* )* 
 ( b* a b* a b* )* 
 
(a b* b b*)* 
Respondido em 07/10/2022 20:20:37 
 
Explicação: 
Gabarito: ( b* a b* a b* )* 
Justificativa: Observe que a única alternativa em que se pode garantir que haverá a ocorrência de zero ou 
outro número par de 'a' é ( b* a b* a b* )*. Nas demais alternativas, sempre é possível gerar uma palavra 
com número ímpar de 'a'. 
 
 
 
 Questão Acerto: 0,0 / 1,0 
 
 
Qual é a linguagem gerada pela gramática S → aSb, S → A, A → aA 
 
 
 
 a
mbn 
 ambm 
 a
nbm 
 a
jbi 
 ∅ 
Respondido em 07/10/2022 20:38:19 
 
Explicação: 
Gabarito: ∅ 
Justificativa: As regras de produção não geram uma cadeia composta apenas de símbolos terminais. 
Portanto, a linguagem gerada é vazia. 
 
 
 
 Questão Acerto: 1,0 / 1,0 
 
 
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: 
 
 
 
 
Produções nulas. 
 Símbolos não geradores e símbolos não alcançáveis. 
 
Cadeia nula. 
 
Símbolos não terminais. 
 
Alfabetos nulos. 
Respondido em 07/10/2022 20:39:38 
 
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. 
 
 
 
 Questão Acerto: 1,0 / 1,0 
 
 
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? 
 
 
 
 
100. 
 
20. 
 
10. 
 
500. 
 40. 
Respondido em 07/10/2022 20:24:21 
 
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. 
 
 
 
 Questão Acerto: 0,0 / 1,0 
 
 
. Em síntese, qualquer programa de computador pode ser traduzido em uma máquina de Turing, e qualquer 
máquina de Turing pode ser traduzida para uma linguagem de programação de propósito geral. Acerca de 
suas características principais, qual item não faz parte do diagrama mecânico da máquina de Turing? 
 
 
 
 
Direção de leitura.. 
 Controle finito. 
 Pilha. 
 
Fita de entrada. 
 
Cabeça de leitura-escrita. 
Respondido em 07/10/2022 20:39:58