AVDS Automatos W

Prévia do material em texto

1a Questão (Ref.: 202014344596) 
 
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 de decisão. 
 
Problema de redução. 
 
Problema de pesquisa. 
 
Problema funcional. 
 
Problema de otimização. 
 
 
 
 
 2a Questão (Ref.: 202014344487) 
 
 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. 
 
 
 
 
 
Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela 
máquina de Turing. 
 
O problema da parada de uma máquina de Turing é 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). 
 
Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G1) ∩ L(G2) = ∅, é 
indecidível. 
 
 
 
 
 3a Questão (Ref.: 202014332340) 
 
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, 8} 
 
{5, 6, 7, 8, 9} 
 
{4, 5, 6, 7} 
 
{4, 5, 6, 7, 8, 9} 
 
{5, 6, 7, 8} 
 
 
 
 
 4a Questão (Ref.: 202014332448) 
 
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. 
 
 
 
 
00c10, 11c11, 01c11, c 
 
00c1, 001c100, 00c10, c 
 
00c00, 1100011, 00100, c 
 
0c0, 11c11, 001c100, c 
 
0c0, 110c111, 001c100, c 
 
 
 
 
 5a Questão (Ref.: 202014332395) 
 
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, 9, 10, 11}. 
 
{5, 6, 7, 8, 10, 11}. 
 
{3, 4, 5, 6, 7, 10, 11}. 
 
{0, 1, 2, 5, 6, 7, 8, 10}. 
 
 
 
 
 6a Questão (Ref.: 202014328028) 
 
A linguagem gerada pelo GLC é chamada de linguagem livre de contexto (LLC). Acerca de suas características, 
a linguagem livre de contexto não é fechada em relação a: 
 
 
 
 
Fechamento de Kleene. 
 
Complementação. 
 
Divisão. 
 
Concatenação. 
 
União. 
 
 
 
 
 7a Questão (Ref.: 202014328198) 
 
(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 
 
aa 
 
aaca 
 
aaaca 
 
ccca 
 
 
 
 
 8a Questão (Ref.: 202014327272) 
 
Considere o seguinte Autômato Finito 
 
Sobre o autômato apresentado, assinale a afirmativa correta. 
 
 
 
 
As palavras com número ímpar de zeros e par de uns são reconhecidas pelo autômato. 
 
As palavras com número par de zeros e ímpar de uns são reconhecidas pelo autômato. 
 
As palavras com número par de zeros e uns são reconhecidas pelo autômato. 
 
As palavras com número ímpar de zeros e uns são reconhecidas pelo autômato. 
 
A palavra vazia é reconhecida pelo autômato. 
 
 
 
 
 9a Questão (Ref.: 202014327273) 
 
Considere o autômato finito mostrado na figura abaixo (os círculos concêntricos representam estado final) e 
assinale a afirmativa correta. 
 
 
 
 
 
A palavra vazia não é reconhecida pelo autômato. 
 
A palavra 101 é reconhecida pelo autômato. 
 
A palavra 10101 é reconhecida pelo autômato. 
 
A palavra vazia é reconhecida pelo autômato. 
 
A palavra 01010 não é reconhecida pelo autômato. 
 
 
 
 
 10a Questão (Ref.: 202014327712) 
 
(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 a afirmativa I é falsa. 
 
Somente as afirmativas II e III são falsas.