LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES AV

Prévia do material em texto

03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS 
 
 
 1. Ref.: 6101664 Pontos: 0,00 / 1,00 
 
BIO-RIO - 2014 - ETAM - Curso de Formação de Técnicos - 1º Semestre 
Considere os conjuntos A = {1, 2, 3, 4, 5} e B = {4, 5, 6, 7, 8, 9} e a função f: A → B 
dada por f(x) = x + 4. O conjunto imagem dessa função é: 
 
 {5, 6, 7, 8, 9} 
 
{4, 5, 6, 7, 8, 9} 
 {5, 6, 7, 8} 
 
{4, 5, 6, 7, 8} 
 
{4, 5, 6, 7} 
 
 
 2. Ref.: 6101719 Pontos: 1,00 / 1,00 
 
CONSULPLAN - 2016 - CBM-PA - Aspirante do Corpo de Bombeiro 
Observe os conjuntos a seguir. 
 
 
 
O conjunto formado pela operação (A - C) ∪ (B ∩ C) é: 
 
 
 
{3, 4, 5, 6, 7, 10, 11}. 
 
{3, 4, 9, 10, 11}. 
 {5, 6, 7, 8, 10, 11}. 
 
{0, 1, 2, 8, 10, 11}. 
 
{0, 1, 2, 5, 6, 7, 8, 10}. 
 
 
 3. Ref.: 6101772 Pontos: 0,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:%206101664.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206101719.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206101772.');
 
00c10, 11c11, 01c11, c 
 
00c00, 1100011, 00100, c 
 
0c0, 110c111, 001c100, c 
 00c1, 001c100, 00c10, 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 
 
 {ancbn|n∈N}{ancbn|n∈ℕ} 
 {acnb|n∈N}{acnb|n∈ℕ} 
 {acbn|n∈N}{acbn|n∈ℕ} 
 {ancnb|n∈N}{ancnb|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. 
 
 abstratas - autômatos - engenharia - compiladores 
 
de estado finito - computadores - TI - computadores 
 
automáticas - compiladores - engenharia - corretores ortográficos 
 
abstratas - compiladores - engenharia - computadores 
 
determinísticas - computadores - matemática - circuitos elétricos 
 
 
 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 a afirmativa III é falsa. 
 
Somente as afirmativas II e III são falsas. 
 
Somente a afirmativa II é falsa. 
 Somente a afirmativa I é 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 
 
I e III 
 
II e IV 
 II 
 
I 
 
 
 8. Ref.: 6097522 Pontos: 1,00 / 1,00 
 
(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. 
 
 
aaaca 
 
ccac 
 
aaca 
 
ccca 
 aa 
 
 
 
 
03494 - COMPUTABILIDADE E A MÁQUINA DE TURING 
 
 
 9. Ref.: 6113714 Pontos: 0,00 / 1,00 
 
Embora uma máquina de Turing seja uma estrutura muito simples, ela é extremamente 
poderosa. Acerca de suas características, uma linguagem L é chamada aceitável, se existe 
uma máquina de Turing M que: 
 
I) Entra em loop infinito para cadeias em L. 
II) Aceita L. 
III) Rejeita L. 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206097522.');
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206113714.');
IV) Resolve o problema em um tempo de execução polinomial. 
V) Resolve o problema da Parada. 
 
 
IV e V. 
 
II e III. 
 
I, III e V. 
 III, IV e V. 
 I, II e III. 
 
 
 10. Ref.: 6113920 Pontos: 1,00 / 1,00 
 
Alan Mathison Turing foi um cientista da computação nascido no Reino Unido que dedicou 
seu trabalho a desenvolver máquinas de computar. Consoante a teoria da computabilidade, 
o problema que resulta em sim ou não é classificado como um: 
 
 
Problema funcional. 
 
Problema de pesquisa. 
 Problema de decisão. 
 
Problema de otimização. 
 
Problema de redução. 
 
javascript:alert('C%C3%B3digo%20da%20quest%C3%A3o:%206113920.');