Linguagens formais, autômatos e compiladores AV 5 de 10

Prévia do material em texto

1a Questão (Ref.: 202009436064) 
 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. 
 
 
 O problema da parada de uma máquina de Turing é indecidível. 
 Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática 
regular, então L(G1) ∩ L(G2) = ∅, é indecidível. 
 É possível construir uma máquina de Turing que aceita qualquer cadeia de 
comprimento par. 
 Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) 
= L(G2). 
 Nenhum procedimento computacional é considerado um algoritmo a menos 
que seja representado pela máquina de Turing. 
 
 
 
 
 
 2a Questão (Ref.: 202009436163) 
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? 
 
 
 Ambos P1 e P2 são decidíveis. 
 Apenas P2 é decidível. 
 Nem P1 nem P2 são decidíveis. 
 Apenas P1 é decidível. 
 P1 e P2 não são problemas de decisão. 
 
 
 
 
 
 3a Questão (Ref.: 202009423917) 
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 é: 
 
 
 {4, 5, 6, 7} 
 {5, 6, 7, 8, 9} 
 {5, 6, 7, 8} 
 {4, 5, 6, 7, 8} 
 {4, 5, 6, 7, 8, 9} 
 
 
 
 
 
 4a Questão (Ref.: 202009424025) 
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, 11c11, 001c100, c 
 0c0, 110c111, 001c100, c 
 00c10, 11c11, 01c11, c 
 00c1, 001c100, 00c10, c 
 00c00, 1100011, 00100, c 
 
 
 
 
 
 5a Questão (Ref.: 202009423972) 
CONSULPLAN - 2016 - CBM-PA - Aspirante do Corpo de Bombeiro 
Observe os conjuntos a seguir. 
 
 
 
O conjunto formado pela operação (A - C) ∪ (B ∩ C) é: 
 
 
 
 {0, 1, 2, 8, 10, 11}. 
 {3, 4, 5, 6, 7, 10, 11}. 
 {5, 6, 7, 8, 10, 11}. 
 {3, 4, 9, 10, 11}. 
 {0, 1, 2, 5, 6, 7, 8, 10}. 
 
 
 
 
 
 6a Questão (Ref.: 202009419774) 
As gramáticas podem ser classificadas de acordo com o seu tipo. Na hierarquia de Chomsky a linguagem livre 
de contexto é a linguagem de: 
 
 
 Tipo 0. 
 Tipo 1. 
 Tipo 3. 
 Tipo 2. 
 Tipo 4. 
 
 
 
 
 
 7a Questão (Ref.: 202009419775) 
(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. 
 
 
 ccac 
 aaaca 
 
ccca 
 aa 
 aaca 
 
 
 
 
 
 8a Questão (Ref.: 202009419351) 
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. 
 
 
 automáticas - compiladores - engenharia - corretores ortográficos 
 determinísticas - computadores - matemática - circuitos elétricos 
 abstratas - compiladores - engenharia - computadores 
 abstratas - autômatos - engenharia - compiladores 
 
de estado finito - computadores - TI - computadores 
 
 
 
 
 
 9a Questão (Ref.: 202009418963) 
(POSCOMP / 2009) Qual é a linguagem da gramática com as seguintes regras de produção: 
S → ASb | c 
A → a 
 
 
 \(\{ a^nc^nb | n \in ℕ \}\) 
 
\(\{ a^ncb | n \in ℕ \}\) 
 \(\{ acb^n | n \in ℕ \}\) 
 \(\{ ac^nb | n \in ℕ \}\) 
 \(\{ a^ncb^n | n \in ℕ \}\) 
 
 
 
 
 
 10a Questão (Ref.: 202009419289) 
(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 III é falsa. 
 Somente a afirmativa II é falsa. 
 Somente as afirmativas I e II são falsas. 
 Somente as afirmativas II e III são falsas. 
 
Somente a afirmativa I é falsa.