LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES

Prévia do material em texto

Disc.: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES   
	Aluno(a): 
	
	Acertos: 7,0 de 10,0
	//2022
		1a
          Questão
	Acerto: 1,0  / 1,0
	
	Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é:
		
	 
	32
	
	64
	
	5
	
	10
	
	16
	Respondido em 01/10/2022 14:14:19
	
	Explicação:
Como sabemos, o número de subconjuntos de um conjunto com n elementos é igual a 2n. Assim, o número de subcadeias de uma cadeia de tamanho 5 será igual a 25 = 32
	
		2a
          Questão
	Acerto: 1,0  / 1,0
	
	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
	
	B X (A U C)
	
	(A U C) X B
	
	C X (A U B)
	
	B X (A ∩ C)
	Respondido em 01/10/2022 14:14:39
	
	Explicação:
A fim de que o produto cartesiano de B com qualquer outro conjunto fosse representado, os pares ordenados devem, necessariamente, iniciar com os elementos do conjunto B = {4, 5}. Como os pares da figura começam com os elementos 1 e 2, as alternativas a e d estão incorretas. A alternativa ¿e¿ nos obrigaria a ter um par ordenado começando com elemento 4. A intersecção dos conjuntos A e C contém os elementos comuns {1, 2}, uma vez que 3 não está contido em C. O produto cartesiano desse conjunto intersecção com o conjunto B é: {(1, 4); (1, 5); (2, 4); (2, 5)}
	
		3a
          Questão
	Acerto: 1,0  / 1,0
	
	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á:
		
	
	81
	
	729
	 
	243
	
	256
	
	64
	Respondido em 01/10/2022 14:14:48
	
	Explicação:
Quando x = 2, ax+1 é igual a a3. O número que elevado ao cubo gera 27 é 3. Logo a função é: y = 3x+1 e a imagem de 4 será: 243 = 35
	
		4a
          Questão
	Acerto: 1,0  / 1,0
	
	(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.
	Respondido em 01/10/2022 14:15:31
	
	Explicação:
Gabarito: somente as igualdades I e II são verdadeiras.
Justificativa: a* + b* significa qualquer combinação de 'a' ou qualquer combinação de 'b', ou seja, as cadeias são formadas apenas por 'a' ou por 'b'. (a + b)* consiste em qualquer combinação de 'a' e 'b', ou seja, as cadeias podem conter os símbolos 'a' e 'b' em sua formação, logo a alternativa III é falsa. A alternativa II é verdadeira porque segundo o fecho de Kleene podemos considerar Σ = {a, b} e Σ* definido como o conjunto de todas as cadeias, incluindo a cadeia nula, portanto as linguagens são iguais e geradas por expressões equivalentes. A alternativa I é, claramente, verdadeira, bastando retirar os parênteses da expressão à direita.
	
		5a
          Questão
	Acerto: 1,0  / 1,0
	
	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?
		
	
	20
	 
	No mínimo 12
	
	No máximo 12
	
	32
	
	36
	Respondido em 01/10/2022 14:14:58
	
	Explicação:
Gabarito: No mínimo 12
Justificativa: O conjunto universo tem 60 alunos. O conjunto dos que gostam de geografia tem 32 e o conjunto dos que gostam de história tem 40. Logo, a intersecção de ambos tem, pelo menos, 12 alunos que gostam de ambas as disciplinas.
	
		6a
          Questão
	Acerto: 1,0  / 1,0
	
	Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta?
		
	
	S U ∅ = ∅
	
	S - ∅ = ∅
	 
	S U ∅ = S - ∅ = S
	
	S ∩ ∅ = S
	
	S U ∅ = S - ∅ = ∅
	Respondido em 01/10/2022 14:15:17
	
	Explicação:
Gabarito: S U ∅ = S - ∅ = S
Justificativa: A união de qualquer conjunto com o conjunto vazio é igual ao próprio conjunto, bem como a diferença de um conjunto com o conjunto vazio é o próprio conjunto. Assim, a única alternativa correta é S U ∅ = S - ∅ = S.
	
		7a
          Questão
	Acerto: 0,0  / 1,0
	
	Seja a seguinte gramática S → aSa | bSb | a | b
Palíndromos são cadeias do tipo wwr, ou seja, aqueles que lidos da esquerda para a direita ou vice e versa, são iguais. A linguagem gerada pela gramática acima sobre o alfabeto {a, b) é o conjunto de:
		
	
	Todos os palíndromos de comprimento par.
	 
	Todos os palíndromos de comprimento ímpar.
	 
	Cadeias que começam e terminam com símbolos diferentes.
	
	Todos os palíndromos.   
	
	A gramática não gera palíndromos.
	Respondido em 01/10/2022 14:22:11
	
	Explicação:
Gabarito: Todos os palíndromos de comprimento ímpar.
Justificativa: Realizando algumas derivações como exemplo pode-se perceber que a alternativa b é a correta, por exemplo: S → aSa → S → aaa; S → aSa → S → abSba → ababa.
	
		8a
          Questão
	Acerto: 0,0  / 1,0
	
	Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC, é denominada de:
		
	 
	Finita.
	
	Irrestrita (sem restrições).
	 
	Infinita.
	
	Recursiva.
	
	Sem contexto.
	Respondido em 01/10/2022 14:20:02
	
	Explicação:
Gabarito: Finita.
Justificativa: Uma linguagem L gerada a partir de uma dada GLC é finita se não houver ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC.
	
		9a
          Questão
	Acerto: 0,0  / 1,0
	
	Seja uma MT T dada pelas quíntuplas:
1. (0, 1, 1, 0, D)
                2. (0, b, 1, 1, H)Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3.
Qual a função que calcula essa MT?
		
	
	2n +1
	 
	2n+1
	
	2n -1
	
	2n
	 
	2n+1 - 1
	Respondido em 01/10/2022 14:21:57
	
	Explicação:
Esse exemplo mostra o poder de computação das MT. Deve-se começar utilizando a quíntupla 1. Enquanto a MT ler 1 na fita, escreve 1, continua no estado 0 e anda para a direita (D). Ao encontrar um branco, escreve 1, muda para o estado final 1 e para (H). A cadeia final é 1111. A cadeia inicial era 111 = 23-1, foi transformada em 1111 = 24-1. Logo a MT calcula 2n+1 - 1
	
		10a
          Questão
	Acerto: 1,0  / 1,0
	
	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?
		
	
	O número de passos (ou tempo) necessários para completar o algoritmo é uma função polinomial de n.
	
	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.
	
	É computável por uma máquina de Turing determinística em tempo polinomial.
	 
	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.
	
	Em geral, a classe P contém todos os problemas que são resolvidos facilmente usando computadores.
	Respondido em 01/10/2022 14:19:18
	
	Explicação:
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 determinística em tempo polinomial.