AVD Compiladores - Estacio

Prévia do material em texto

AVD Compiladores – 10 pontos 
 
 1a Questão (Ref.: 202109872458) 
Considere dois problemas de decisão PA e PB, sendo PA indecidível e PB decidível. Observe 
também dois problemas de decisão PC e PD, cuja decidibilidade é desconhecida. Suponha que 
seja possível construir de forma correta as seguintes reduções: 
• de PA para PC. 
• de PD para PA. 
• de PD para PB. 
Com base no cenário descrito, assinale a alternativa correta. 
 
 
 
Não se pode afirmar nada sobre a decidibilidade dos problemas PC e PD. 
 
PC e PD são ambos indecidíveis. 
 
Não se pode afirmar nada sobre a decidibilidade de PC, porém PD é decidível. 
 
PC é indecidível e PD é decidível. 
 
PC é indecidível, contudo não se pode afirmar nada sobre a decidibilidade de PD. 
 
 
 
 2a Questão (Ref.: 202109872548) 
 Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens 
da hierarquia de Chomsky e suas respectivas máquinas reconhecedoras, analise as afirmações 
a seguir e assinale a falsa. 
 
 
 
Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2). 
 
Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G1) 
∩ L(G2) = ∅, é indecidível. 
 
Nenhum procedimento computacional é considerado um algoritmo a menos que seja 
representado pela máquina de Turing. 
 
É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento 
par. 
 
O problema da parada de uma máquina de Turing é indecidível. 
 
 
 
 
 
 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113721/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 3a Questão (Ref.: 202109860646) 
Palíndromos são cadeias que lidas da esquerda para a direita ou da direita para a esquerda 
têm a mesma sequência de símbolos e podem ser definidas pela seguinte expressão: wwR, 
onde w é uma cadeia e não há constante ou separador. Nesse contexto, assinale a 
alternativa em que todas as cadeias são palíndromos sem separador. 
 
 
001, 1190911, 0010, AABB 
 
00, 119911, 001100, AA 
 
001, 1199911, 0010, AABB 
 
010, 1190911, 00100, ANA 
 
ANA, 1190911, 0010, ABA 
 
 
 4a Questão (Ref.: 202109860676) 
Seja G = (V, T, P, E), onde V = {+, *, (, ), id, T, F, E}, T = {+, *, (, ), id} e P: 
 
1. E → E + T 4. T → F 
2. E → T 5. F → (E) 
3. T → T * F 6. F → id 
 Os símbolos E, T, F são abreviaturas para expressão, termo e fator, respectivamente e id é 
um identificador válido dessa linguagem. 
 Assinale a alternativa que tem uma derivação correta para a expressão id + (id * id): 
 
 
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id / (id - 
id). 
 
E =>1 E + T =>3 E + T * F =>5 E + T * (E) =>1 E + T * (E + T) =>2 T * (T + T) =>4 F 
* (F + F) =>6 id * (id + id). 
 
T =>4 F =>5 (E) =>1(E + T) =>3 (E + T*F) =>4 (F + F*F) =>6 (id + id *id). 
 
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id 
+ id). 
 
E =>1 E + T =>2 T + T =>4 T + F =>5 T + (E) =>2 T + (T) =>3 T + (T * F) =>4 F + (F 
* F) =>6 id + (id * id). 
 
 
 5a Questão (Ref.: 202109860509) 
Considere a seguinte gramática: G = {S, (0, 1, c), (S→0S0, S→1S1, S→c), S}. Assinale a 
alternativa que contém, apenas, cadeias geradas por essa gramática. 
 
 
0c0, 110c111, 001c100, c 
 
00c00, 1100011, 00100, c 
 
0c0, 11c11, 001c100, c 
 
00c1, 001c100, 00c10, c 
 
00c10, 11c11, 01c11, c 
 
 
 
 
 
 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101909/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 6a Questão (Ref.: 202109856087) 
(ENADE / 2011) 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 é sempre 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: 
 
 
II 
 
II e IV 
 
I 
 
III e IV 
 
I e III 
 
 
 7a Questão (Ref.: 202109856259) 
(POSCOMP / 2008) Considere a seguinte gramática G, onde S é o símbolo inicial: 
 S → AcB 
 A → cA | aB 
 B → cB | aA 
 A → λ 
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela 
gramática G. 
 
 
ccca 
 
ccac 
 
aa 
 
aaca 
 
aaaca 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097522/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 8a Questão (Ref.: 202109855447) 
(POSCOMP / 2009) Qual é a linguagem da gramática com as seguintes regras de produção: 
S → ASb | c 
A → a 
 
 {ancnb|n∈N}{ancnb|n∈ℕ} 
 {ancbn|n∈N}{ancbn|n∈ℕ} 
 {acbn|n∈N}{acbn|n∈ℕ} 
 {acnb|n∈N}{acnb|n∈ℕ} 
 {ancb|n∈N}{ancb|n∈ℕ} 
 
 
 9a Questão (Ref.: 202109855835) 
A teoria dos autômatos é o estudo de máquinas _______________ e os problemas 
computacionais relacionados a essas máquinas, chamadas de _______________. São 
aplicados em diferentes áreas da ciência da computação e da _______________. Sua 
aplicação mais tradicional é encontrada na construção de _______________. 
Assinale a alternativa que preenche, correta e respectivamente, as lacunas do trecho acima. 
 
 
de estado finito - computadores - TI - computadores 
 
abstratas - compiladores - engenharia - computadores 
 
abstratas - autômatos - engenharia - compiladores 
 
determinísticas - computadores - matemática - circuitos elétricos 
 
automáticas - compiladores - engenharia - corretores ortográficos 
 
 
 10a Questão (Ref.: 202109855773) 
(POSCOMP / 2008) Seja o autômato finito mostrado na figura abaixo que opera sobre o 
alfabeto Σ = {a,b} (o círculo em negrito indica um estado terminal): 
 
Analise as seguintes afirmativas. 
I. O autômato finito mostrado na figura é determinístico. 
II. O autômato finito mostrado na figura é não-determinístico. 
III. O autômato finito mostrado na figura reconhece a palavra vazia 
A análise permite concluir que 
 
 
Somente a afirmativa II é falsa. 
 
Somente a afirmativa I é falsa. 
 
Somente as afirmativas I e II são falsas. 
 
Somente as afirmativas II e III são falsas. 
 
Somente a afirmativa III é falsa. 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096710/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036/n/nStatus da quest%C3%A3o: Liberada para Uso.');