AVDS Automâtas

Prévia do material em texto

1a Questão (Ref.: 201908674462) 
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. 
 
 
 
PC é indecidível e PD é decidível. 
 
PC e PD são ambos indecidíveis. 
 
PC é indecidível, contudo não se pode afirmar nada sobre a decidibilidade de PD. 
 
Não se pode afirmar nada sobre a decidibilidade dos problemas PC e PD. 
 
Não se pode afirmar nada sobre a decidibilidade de PC, porém PD é decidível. 
 
 
 
 2a Questão (Ref.: 201908674651) 
Considere os seguintes problemas de decisão: 
 
P1: Uma determinada máquina de estado finito aceita uma determinada cadeia. 
P2: Uma determinada gramática livre de contexto gera um número infinito de cadeias. 
 
Qual das seguintes afirmações é verdadeira? 
 
 
Nem P1 nem P2 são decidíveis. 
 
P1 e P2 não são problemas de decisão. 
 
Ambos P1 e P2 são decidíveis. 
 
Apenas P1 é decidível. 
 
Apenas P2 é decidível. 
 
 
 
 3a Questão (Ref.: 201908662650) 
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. 
 
 
00, 119911, 001100, AA 
 
001, 1190911, 0010, AABB 
 
ANA, 1190911, 0010, ABA 
 
001, 1199911, 0010, AABB 
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: 6113910/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101909/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
010, 1190911, 00100, ANA 
 
 
 
 4a Questão (Ref.: 201908662680) 
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 =>4 F =>5 (E) =>1(E + T) =>3 (E + T*F) =>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). 
 
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>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 =>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). 
 
 
 
 5a Questão (Ref.: 201908662513) 
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 
 
00c1, 001c100, 00c10, c 
 
00c10, 11c11, 01c11, c 
 
00c00, 1100011, 00100, c 
 
0c0, 11c11, 001c100, c 
 
 
 
 6a Questão (Ref.: 201908658091) 
(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. 
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.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 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: 
 
 
III e IV 
 
II 
 
II e IV 
 
I e III 
 
I 
 
 
 
 7a Questão (Ref.: 201908658261) 
Se ∑ = {1}, então ∑* - ∑+ é 
 
 
1* 
 
λ 
 
{1} 
 
{λ, 1, 11¿..} 
 
1+ 
 
 
 
 8a Questão (Ref.: 201908657451) 
(POSCOMP / 2009) Qual é a linguagem da gramática com as seguintes regras de produção: 
S → ASb | c 
A → a 
 
 {acnb|n∈N}{acnb|n∈ℕ} 
 {ancnb|n∈N}{ancnb|n∈ℕ} 
 {acbn|n∈N}{acbn|n∈ℕ} 
 {ancbn|n∈N}{ancbn|n∈ℕ} 
 {ancb|n∈N}{ancb|n∈ℕ} 
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097520/n/nStatus da quest%C3%A3o: Liberada para Uso.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096710/n/nStatus da quest%C3%A3o: Liberada para Uso.');
 
 
 9a Questão (Ref.: 201908657839) 
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 
 
determinísticas - computadores - matemática - circuitos elétricos 
 
automáticas - compiladores - engenharia - corretores ortográficos 
 
abstratas - compiladores - engenharia - computadores 
 
abstratas - autômatos - engenharia - compiladores 
 
 
 
 10a Questão (Ref.: 201908657777) 
(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 as afirmativas I e II são falsas. 
 
Somente as afirmativas II e III são falsas. 
 
Somente a afirmativa III é falsa. 
 
Somente a afirmativa I é falsa. 
 
Somente a afirmativa II é falsa. 
 
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.');