LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES AV ESTÁCIO

Prévia do material em texto

03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
	 
	 
	 1.
	Ref.: 6101664
	Pontos: 1,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}
	
	{4, 5, 6, 7, 8, 9}
	
	{4, 5, 6, 7, 8}
	
	{5, 6, 7, 8}
	
	
	 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, 9, 10, 11}.
	
	{3, 4, 5, 6, 7, 10, 11}.
	
	{0, 1, 2, 5, 6, 7, 8, 10}.
	
	{0, 1, 2, 8, 10, 11}.
	 
	{5, 6, 7, 8, 10, 11}.
	
	
	 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.
		
	
	00c1, 001c100, 00c10, c
	
	00c10, 11c11, 01c11, c
	
	0c0, 110c111, 001c100, c
	
	00c00, 1100011, 00100, c
	 
	0c0, 11c11, 001c100, c
	
	
	 
		
	03492 - LINGUAGENS REGULARES
	 
	 
	 4.
	Ref.: 6096597
	Pontos: 1,00  / 1,00
	
	Considere o autômato finito mostrado na figura abaixo (os círculos concêntricos representam estado final) e assinale a afirmativa correta.
		
	
	A palavra 01010 não é reconhecida pelo autômato.
	
	A palavra vazia não é reconhecida  pelo autômato.
	
	A palavra 10101 é reconhecida pelo autômato.
	
	A palavra 101 é reconhecida pelo autômato.
	 
	A palavra vazia é reconhecida pelo autômato.
	
	
	 5.
	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
		
	
	{acbn|n∈N}{acbn|n∈ℕ}
	
	{acnb|n∈N}{acnb|n∈ℕ}
	 
	{ancbn|n∈N}{ancbn|n∈ℕ}
	
	{ancnb|n∈N}{ancnb|n∈ℕ}
	
	{ancb|n∈N}{ancb|n∈ℕ}
	
	
	 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):
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 II é falsa.
	 
	Somente a afirmativa I é falsa.
	
	Somente a afirmativa III é falsa.
	
	Somente as afirmativas II e III são falsas.
	
	Somente as afirmativas I e II são falsas.
	
	
	 
		
	03493 - LINGUAGENS LIVRES DE CONTEXTO
	 
	 
	 7.
	Ref.: 6097352
	Pontos: 1,00  / 1,00
	
	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:
		
	
	União.
	
	Concatenação.
	
	Divisão.
	 
	Complementação.
	
	Fechamento de Kleene.
	
	
	 8.
	Ref.: 6097520
	Pontos: 1,00  / 1,00
	
	Se ∑ = {1}, então ∑* - ∑+ é
		
	
	1+
	 
	λ
	
	1*
	
	{1}
	
	{λ, 1, 11¿..}
	
	
	 
		
	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, contudo não se pode afirmar nada sobre a decidibilidade de PD.
	
	Não se pode afirmar nada sobre a decidibilidade de PC, porém PD é decidível.
	 
	PC é indecidível e PD é decidível.
	
	PC e PD são ambos indecidíveis.
	
	Não se pode afirmar nada sobre a decidibilidade dos problemas PC e PD.
	
	
	 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 de otimização.
	 
	Problema de decisão.
	
	Problema de pesquisa.
	
	Problema funcional.
	
	Problema de redução.