LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES nota 9,00

Prévia do material em texto

LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES 
	Período: 2022.2 (G) / SM
	
	
	
		Quest.: 1
	
		1.
		Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é:
	
	
	
	
	5
	
	
	64
	
	
	16
	
	
	10
	
	
	32
	
	
	
		Quest.: 2
	
		2.
		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 U C) X B
	
	
	C X (A U B)
	
	
	B X (A U C)
	
	
	(A ∩ C) X B
	
	
	B X (A ∩ C)
	
	
	
		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á:
	
	
	
	
	729
	
	
	64
	
	
	81
	
	
	256
	
	
	243
	
	
	
		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?
	
	
	
	
	No máximo 12
	
	
	32
	
	
	36
	
	
	20
	
	
	No mínimo 12
	
	
	
		Quest.: 5
	
		5.
		Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta?
	
	
	
	
	S U ∅ = ∅
	
	
	S U ∅ = S - ∅ = ∅
	
	
	S ∩ ∅ = 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 III é verdadeira.
	
	
	somente as igualdades I e II são verdadeiras.
	
	
	somente as igualdades II e III são verdadeiras.
	
	
	somente a igualdade I é verdadeira.
	
	
	somente a igualdade II é verdadeira.
	
	
	
		Quest.: 7
	
		7.
		A Forma Normal de Chomsky é um outro tipo de forma normal, além da BNF. Qual das seguintes produções está em CNF (NT = Não Terminal)?
	
	
	
	
	(NT) → (Cadeia de cinco ou mais NT)
	
	
	(NT) → (Cadeia de exatamente três terminais)
	
	
	(NT) → (Cadeia de exatamente dois NT)
	
	
	(NT) → (Cadeia de exatamente quatro terminais)
	
	
	(NT) → (Cadeia de um terminal e três não terminais)
	
	
	
		Quest.: 8
	
		8.
		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 (1) justifica a (2).
	
	
	Ambas as proposições são falsas.
	
	
	A proposição (1) é verdadeira e (2) é falsa.
	
	
	As proposições (1) e (2) são verdadeiras, sendo que a (2) justifica a (1).
	
	
	As proposições (1) e (2) são verdadeiras, sendo que a (2) não justifica a (1).
	
	
	
		Quest.: 9
	
		9.
		Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo é quadrático, quanto tempo em segundos ele gastará, aproximadamente, no mesmo computador, se a entrada tiver tamanho 100?
	
	
	
	
	10.
	
	
	100.
	
	
	20.
	
	
	40.
	
	
	500.
	
	
	
		Quest.: 10
	
		10.
		Existem dois tipos principais de complexidade computacional para um algoritmo: complexidade de tempo e complexidade do espaço. Nesse sentido, o que é falso para o problema da classe P?
	
	
	
	
	Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de execução é limitado por um polinômio.
	
	
	Em geral, a classe P contém todos os problemas que são resolvidos facilmente usando computadores.
	
	
	P é definido como o conjunto de todos os problemas de decisão para os quais existe um algoritmo que pode ser realizado por uma máquina de Turing não-determinística em tempo polinomial.
	
	
	O número de passos (ou tempo) necessários para completar o algoritmo é uma função polinomial de n.
	
	
	É computável por uma máquina de Turing determinística em tempo polinomial.