EXERCICIO 2

Prévia do material em texto

03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
	 
		
	
		1.
		Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é:
	
	
	
	16
	
	
	64
	
	
	10
	
	
	5
	
	
	32
	Data Resp.: 04/12/2023 17:29:52
		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
	
	
	 
		
	
		2.
		Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
(a, b)+ significa
	
	
	
	Qualquer combinação de a, b, mas 'a' virá primeiro
	
	
	Qualquer combinação de a, b excluindo nulo
	
	
	Qualquer combinação de a, b incluindo nulo
	
	
	Qualquer combinação de a, b, mas 'b' virá primeiro
	
	
	λ
	Data Resp.: 04/12/2023 17:30:02
		Explicação: 
Utilizando o fecho de Kleene, sabemos que a expressão (a, b)+ gera qualquer combinação de cadeias compostas pelos símbolos a e b e, necessariamente, não inclui a cadeia nula λ. Neste caso, a ordem em que aparecem os símbolos nas cadeias não requer que "a" venha antes de "b". Se isso fosse necessário escreveríamos (ab)+
	
	
	 
		
	
		3.
		Considere as afirmativas abaixo e marque a única alternativa correta:
 
I. um conjunto finito e não vazio Σ de símbolos, é chamado de alfabeto.
II. A partir dos símbolos individuais nós construímos cadeias, que são sequências finitas ou infinitas de símbolos do alfabeto, concatenados.
III. Uma linguagem formal é um conjunto, finito ou infinito, de cadeias, formadas pela concatenação de elementos de um alfabeto finito e não-vazio.
	
	
	
	Apenas as alternativas II e III estão corretas
	
	
	Apenas a alternativa II está correta
	
	
	Apenas as alternativas I e II estão corretas
	
	
	Apenas a alternativa III está correta
	
	
	As alternativas I, II e III estão corretas
	Data Resp.: 04/12/2023 17:32:09
		Explicação: 
Um alfabeto é um conjunto finito e não vazio de símbolos. Os símbolos formam as cadeias por meio da operação de concatenação. Um conjunto, finito ou infinito, de cadeias, formadas pela concatenação de elementos de um alfabeto finito e não-vazio é uma linguagem formal. De acordo com o exposto no texto, todas as alternativas estão corretas.
	
	
	 
		
	
		4.
		Sejam os conjuntos A com 2 elementos, B com 4 elementos, C com 5 elementos, então:
	
	
	
	A ∩ B tem no máximo 1 elemento
	
	
	A ∪ C tem no máximo 5 elementos
	
	
	A ∩ ∅ tem 3 elementos pelo menos
	
	
	(A ∪ B) ∪ C tem no máximo 2 elementos
	
	
	(A ∩ B) ∩ C tem no máximo 2 elementos
	Data Resp.: 04/12/2023 17:32:59
		Explicação: 
A intersecção de A com B tem no máximo dois elementos, uma vez que o conjunto A só tem dois elementos. Essa intersecção pode ter zero, um ou dois elementos. Isto pode ser visto desenhando um diagrama de Venn. A U B terá seis elementos e A U C terá sete elementos. Como C tem 5 elementos, mas a intersecção de A com B tem, no máximo dois elementos, então (A ∩ B) ∩ C tem, no máximo 2 elementos.
	
	
	 
		
	
		5.
		A análise sintática é usualmente implementada a partir de uma gramática:
	
	
	
	Irrestrita
	
	
	Com estrutura de frase
	
	
	Livre de contexto
	
	
	Regular
	
	
	Sensível ao contexto
	Data Resp.: 04/12/2023 17:33:33
		Explicação: 
As gramáticas regulares são utilizadas para a análise léxica em compiladores de linguagens de programação. A parte gramatical da linguagem é verificada por meio de árvores de derivação geradas a partir de gramáticas livres de contexto.
	
	
	 
		
	
		6.
		Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
Qual o tipo da seguinte gramática: S → aSb  e S → ab
	
	
	
	Regular
	
	
	Irrestrito
	
	
	Livre de Contexto
	
	
	Com estrutura de frase
	
	
	Sensível ao Contexto
	Data Resp.: 04/12/2023 17:34:49
		Explicação: 
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção atendendo às seguintes restrições: 1. Todas as regras de produção devem ser do tipo (Não-terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 1. A gramática do enunciado atende a essas duas restrições.
	
	
	 
		
	
		7.
		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
	
	
	B X (A U C)
	
	
	(A ∩ C) X B
	
	
	B X (A ∩ C)
	
	
	C X (A U B)
	Data Resp.: 04/12/2023 17:35:41
		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)}
	
	
	 
		
	
		8.
		Considere as seguintes regras de gramática, onde "|" representa "ou", λ representa a cadeia vazia e undrscr é o caractere "_".
 
1. → 
2. →   
3. → 
4. →   
5. →   
6. →  λ
7. → a | b | ... | z | A | B | ... | Z
8. → 0 | 1 | ... | 9
9. → _
 
Assinale a cadeia que pode ser gerada pela aplicação das produções na seguinte ordem:1, 7, 3, 7, 5, 9, 4, 8, 6
	
	
	
	a0
	
	
	7b1
	
	
	_ab9
	
	
	ab_9
	
	
	ab_
	Data Resp.: 04/12/2023 17:35:58
		Explicação: 
Sabemos que as cadeias são geradas a partir do emprego das regras de produção. Aplicando a regra 1 temos ⇒. Na sequência aplica-se a regra 7 onde foi substituída por uma letra, portanto, fica estabelecido que essa cadeia irá iniciar por uma letra, o que já elimina as alternativas "d" e "e". Neste ponto estamos em a, supondo que a letra que foi substituída é "a" já que todas as alternativas iniciam com a letra "a". Em seguida, é aplicada a regra 3   e ficamos com a cadeia a< resto >.
Aplicando a regra 7 substituímos a por "b", o que elimina a alternativa "b". Neste ponto estamos com a cadeia ab. Aplicando a regra 5 ficamos com ab . Pela regra 9 geramos ab_. Pela regra 4 ab_. A regra 8 aplicada gera ab_9, ou qualquer outro dígito, mas para o caso em questão nos interessa o 9.
Ao aplicar a regra 6 substituímos pela cadeia nula (λ) e geramos ab_9.
As produções podem ser desenvolvidas como segue:
⇒⇒a⇒a ⇒ ab ⇒ ab
⇒ab_⇒ab_ ⇒ab_9.
	
	
	 
		
	
		9.
		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á: 
	
	
	
	64
	
	
	81
	
	
	243
	
	
	729
	
	
	256
	Data Resp.: 04/12/2023 17:36:04
		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
	
	
	 
		
	
		10.
		Considere, a seguir, a gramática livre de contexto G = (V, T, P, S), onde V = {S}, T = {a,b,c}, e P:
S → aS|Sb|c
Qual expressão regular gera a mesma linguagem que a gramática definida acima?
	
	
	
	an c bm, onde n, m ≥ 1
	
	
	an c bm, onde n, m ≥ 0
	
	
	a+ b+ c
	
	
	ca+ b+
	
	
	anc bn, onde n ≥ 0
	Data Resp.: 04/12/2023 17:36:12
		Explicação: 
Aplicando algumas regras de produção podemos inferir a lei geral de formação de cadeias dessa linguagem. S → c. Isso equivale a λcλ. Logo n, m ≥ 0, eliminamos as alternativas de a) até c), uma vez que pode haver cadeias sem símbolos ¿a¿ e/ou ¿b¿. Sejam os exemplos: S → aS⇒ac e S → Sb⇒cb. Esses dois exemplos nos mostram que as cadeias dessa linguagempodem ter números diferentes de símbolos ¿a¿ e ¿b¿, indicando que a alternativa d está errada.