EXERCICIO 3

Prévia do material em texto

03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
	 
		
	
		1.
		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 → aS/A
aS → aa
A → a
	
	
	
	Livre de Contexto
	
	
	Regular
	
	
	Com estrutura de frase
	
	
	Irrestrito
	
	
	Sensível ao Contexto
	Data Resp.: 04/12/2023 17:37:45
		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 tem uma regra que torna sensível ao contexto, ao ter um símbolo não-terminal do lado esquerdo da produção.
	
	
	 
		
	
		2.
		Referência: elaborado pelo autor, 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, mas 'b' virá primeiro
	
	
	Qualquer combinação de a, b incluindo nulo
	
	
	λ
	
	
	Qualquer combinação de a, b excluindo nulo
	Data Resp.: 04/12/2023 17:38:01
		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, 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.
		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
	
	
	
	Com estrutura de frase
	
	
	Sensível ao Contexto
	
	
	Irrestrito
	
	
	Livre de Contexto
	
	
	Regular
	Data Resp.: 04/12/2023 17:38:11
		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.
	
	
	 
		
	
		4.
		Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
Qual a linguagem gerada pela gramática: G = {(S, A), (0, 1), (S→0S1, S→A, A→0A), S}.
	
	
	
	0m1m
	
	
	λ
	
	
	1m0n
	
	
	1m0m
	
	
	0m1n
	Data Resp.: 04/12/2023 17:38:16
		Explicação: 
Observe que não existe uma regra de produção que possa nos levar a um símbolo terminal apenas. Todas as regras de produção, se aplicadas, nos levam a cadeias compostas de terminais e não terminais. Sendo impossível gerar cadeias formadas apenas de terminais, essa é uma linguagem vazia.
	
	
	 
		
	
		5.
		Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
Qual é o maior número de tipo para a gramática dada pelas seguintes regras de produção S → Aa, A → c | Ba, B → abc.
	
	
	
	Zero
	
	
	Quatro
	
	
	Dois
	
	
	Um
	
	
	Três
	Data Resp.: 04/12/2023 17:38:45
		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.
	
	
	 
		
	
		6.
		A análise sintática é usualmente implementada a partir de uma gramática:
	
	
	
	Sensível ao contexto
	
	
	Irrestrita
	
	
	Regular
	
	
	Livre de contexto
	
	
	Com estrutura de frase
	Data Resp.: 04/12/2023 17:38:54
		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.
	
	
	 
		
	
		7.
		Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é:
	
	
	
	10
	
	
	16
	
	
	32
	
	
	64
	
	
	5
	Data Resp.: 04/12/2023 17:39:24
		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
	
	
	 
		
	
		8.
		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
	
	
	(A ∩ C) X B
	
	
	B X (A U C)
	
	
	C X (A U B)
	
	
	B X (A ∩ C)
	Data Resp.: 04/12/2023 17:39:30
		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)}
	
	
	 
		
	
		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
	
	
	729
	
	
	81
	
	
	243
	
	
	256
	Data Resp.: 04/12/2023 17:39:34
		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 ≥ 0
	
	
	a+ b+ c
	
	
	an c bm, onde n, m ≥ 1
	
	
	anc bn, onde n ≥ 0
	
	
	ca+ b+
	Data Resp.: 04/12/2023 17:40:16
		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 linguagem podem ter números diferentes de símbolos ¿a¿ e ¿b¿, indicando que a alternativa d está errada.
	
	
	 
	 
	Não Respondida
	 
	 
	 Não Gravada
	 
	 
	Gravada