LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES - NOTA 10

Prévia do material em texto

Disciplina: ARA0309 - LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES 
	Período: 2022.2 (G) / SM
	
	
	
		Quest.: 1
	
		1.
		BIO-RIO - 2014 - ETAM - Curso de Formação de Técnicos - 2º Semestre
Dados três conjuntos, A = {1,2,3}, B = {4,5} e C = {1,2,4}, observe os pares ordenados apresentados graficamente na figura abaixo.
 
 
Esses pares correspondem, graficamente, a:
	
	
	
	
	(A ∩ C) X B
	
	
	(A U C) X B
	
	
	B X (A U C)
	
	
	C X (A U B)
	
	
	B X (A ∩ C)
	
	
	
		Quest.: 2
	
		2.
		Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é:
	
	
	
	
	10
	
	
	32
	
	
	64
	
	
	5
	
	
	16
	
	
	
		Quest.: 3
	
		3.
		Câmara Municipal de Marabá- Engenheiro Civil - FADESP-2021
A função exponencial y = ax+1 é tal que a imagem de 2 é 27. A imagem de 4 será:
	
	
	
	
	243
	
	
	81
	
	
	64
	
	
	729
	
	
	256
	
	
	
		Quest.: 4
	
		4.
		Vamos considerar que em uma classe 32 alunos gostam de Geografia e 40 de História. Sabendo que a classe possui 60 alunos, qual o número de alunos que gostam de Geografia e de História?
	
	
	
	
	32
	
	
	No máximo 12
	
	
	20
	
	
	No mínimo 12
	
	
	36
	
	
	
		Quest.: 5
	
		5.
		Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta?
	
	
	
	
	S - ∅ = ∅
	
	
	S U ∅ = S - ∅ = ∅
	
	
	S U ∅ = S - ∅ = S
	
	
	S U ∅ = ∅
	
	
	S ∩ ∅ = S
	
	
	
		Quest.: 6
	
		6.
		(POSCOMP / 2008 - adaptada) Analise as seguintes igualdades de expressões regulares:
I. a* = (a)*
II. (a+b)* = (b+a)*
III. a*+b* = (a+b)*
A análise permite concluir que
	
	
	
	
	somente a igualdade II é verdadeira.
	
	
	somente as igualdades I e II são verdadeiras.
	
	
	somente a igualdade III é verdadeira.
	
	
	somente as igualdades II e III são verdadeiras.
	
	
	somente a igualdade I é verdadeira.
	
	
	
		Quest.: 7
	
		7.
		Avalie as proposições (1) e (2) a seguir:
(1) Uma linguagem L gerada a partir de uma dada GLC é infinita
(2) se houver pelo menos um ciclo no grafo direcionado gerado a partir das regras de produção dessa GLC
A esse respeito, assinale a afirmativa VERDADEIRA.
	
	
	
	
	As proposições (1) e (2) são verdadeiras, sendo que a (2) não justifica a (1).
	
	
	A proposição (1) é verdadeira e (2) é falsa.
	
	
	As proposições (1) e (2) são verdadeiras, sendo que a (2) justifica a (1).
	
	
	Ambas as proposições são falsas.
	
	
	As proposições (1) e (2) são verdadeiras, sendo que a (1) justifica a (2).
	
	
	
		Quest.: 8
	
		8.
		Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias.  Nesse sentido, assinale a alternativa incorreta.
	
	
	
	
	λ ∈ Σ*
	
	
	V ∩ T = ∅
	
	
	V U T = Σ
	
	
	V ∩ T = Σ*
	
	
	a + b denota {a} U {b} = {a, b}
	
	
	
		Quest.: 9
	
		9.
		Analise as seguintes afirmativas
 
I. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão. Em um problema de localização, procura-se localizar uma certa estrutura que satisfaça um conjunto de propriedades dadas. Se as propriedades envolverem critérios de otimização, então o problema é dito de otimização.
II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-completos é aplicado somente para esse tipo de problema.
III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP podem ser resolvidos da mesma forma.
A análise permite concluir que:
	
	
	
	
	Apenas as afirmativas I e II estão corretas.
	
	
	Apenas as afirmativas I e III estão corretas.
	
	
	Apenas a afirmativa I está correta.
	
	
	As afirmativas I, II e III estão corretas.
	
	
	Apenas a afirmativa II está correta.
	
	
	
		Quest.: 10
	
		10.
		Com base nas afirmativas abaixo sobre a descrição instantânea (DI) da máquina de Turing assinale a resposta correta:
 
I. Lembra o estado da máquina.
II. Lembra da célula que está sendo digitalizada pelo cabeçote de leitura e gravação.
III. O conteúdo de todas as células da fita.
IV. O conteúdo da célula seguinte a que está sendo lida.
	
	
	
	
	II e IV, apenas
	
	
	I, II e III, apenas
	
	
	II e III, apenas
	
	
	I, II e IV, apenas
	
	
	I e IV, apenas.