AVS Linguagens formais, Automâtos e Compiladores

Prévia do material em texto

03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS 
 
 
 1. Ref.: 6101909 Pontos: 1,00 / 1,00 
 
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 
 
010, 1190911, 00100, ANA 
 
 
 2. Ref.: 6101939 Pontos: 1,00 / 1,00 
 
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). 
 
 
 3. Ref.: 6101772 Pontos: 1,00 / 1,00 
 
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. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206101909.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206101939.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206101772.');
 
 
0c0, 110c111, 001c100, c 
 
00c1, 001c100, 00c10, c 
 
00c10, 11c11, 01c11, c 
 
00c00, 1100011, 00100, c 
 0c0, 11c11, 001c100, c 
 
 
 
 
03492 - LINGUAGENS REGULARES 
 
 
 4. Ref.: 6096710 Pontos: 1,00 / 1,00 
 
(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∈ℕ} 
 
 
 5. Ref.: 6097098 Pontos: 1,00 / 1,00 
 
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 
 
 
 6. Ref.: 6097036 Pontos: 1,00 / 1,00 
 
(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): 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206096710.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206097098.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206097036.');
 
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. 
 
 
 
 
03493 - LINGUAGENS LIVRES DE CONTEXTO 
 
 
 7. Ref.: 6097350 Pontos: 1,00 / 1,00 
 
(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. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206097350.');
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 
 
 
 8. Ref.: 6097520 Pontos: 1,00 / 1,00 
 
Se ∑ = {1}, então ∑* - ∑+ é 
 
 
1* 
 λ 
 
{1} 
 
{λ, 1, 11¿..} 
 
1+ 
 
 
 
 
03494 - COMPUTABILIDADE E A MÁQUINA DE TURING 
 
 
 9. Ref.: 6113721 Pontos: 1,00 / 1,00 
 
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. 
 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206097520.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206113721.');
 10. Ref.: 6113910 Pontos: 1,00 / 1,00 
 
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. 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206113910.');