EXERCICIO 1

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 maior número de tipo para a gramática dada pelas seguintes regras de produção S → Aa, A → c | Ba, B → abc.
	
	
	
	Três
	
	
	Quatro
	
	
	Dois
	
	
	Zero
	
	
	Um
	Data Resp.: 04/12/2023 17:14: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.
	
	
	 
		
	
		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 'b' virá primeiro
	
	
	Qualquer combinação de a, b excluindo nulo
	
	
	Qualquer combinação de a, b, mas 'a' virá primeiro
	
	
	λ
	
	
	Qualquer combinação de a, b incluindo nulo
	Data Resp.: 04/12/2023 17:17:24
		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
	
	
	Irrestrito
	
	
	Livre de Contexto
	
	
	Sensível ao Contexto
	
	
	Regular
	Data Resp.: 04/12/2023 17:19:04
		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 o tipo da seguinte gramática?
 
S → aS/A
aS → aa
A → a
	
	
	
	Irrestrito
	
	
	Com estrutura de frase
	
	
	Sensível ao Contexto
	
	
	Regular
	
	
	Livre de Contexto
	Data Resp.: 04/12/2023 17:20:01
		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.
	
	
	 
		
	
		5.
		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?
	
	
	
	anc bn, onde n ≥ 0
	
	
	ca+ b+
	
	
	an c bm, onde n, m ≥ 1
	
	
	an c bm, onde n, m ≥ 0
	
	
	a+ b+ c
	Data Resp.: 04/12/2023 17:21:14
		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.
	
	
	 
		
	
		6.
		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}.
	
	
	
	1m0m
	
	
	λ
	
	
	1m0n
	
	
	0m1n
	
	
	0m1m
	Data Resp.: 04/12/2023 17:21:45
		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.
	
	
	 
		
	
		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
	
	
	C X (A U B)
	
	
	B X (A U C)
	
	
	(A ∩ C) X B
	
	
	B X (A ∩ C)
	Data Resp.: 04/12/2023 17:22:28
		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
	
	
	_ab9
	
	
	ab_
	
	
	7b1
	
	
	ab_9
	Data Resp.: 04/12/2023 17:23:14
		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á: 
	
	
	
	729
	
	
	81
	
	
	243
	
	
	64
	
	
	256
	Data Resp.: 04/12/2023 17:23:44
		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.
		Referência: elaborado pelo autor, adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
 
Assinale a alternativa correta
	
	
	
	a* = a+. a*
	
	
	a+ = a*. a
	
	
	a+ = a*. a*
	
	
	a = a + a
	
	
	a* = a+. a+
	Data Resp.: 04/12/2023 17:24:30Explicação: 
De acordo com o fecho de Kleene, a* são todas as cadeias formadas por um número indeterminado de "a", incluindo a cadeia nula λ. Todas as cadeias formadas por um número indeterminado de "a", não incluindo a cadeia nula λ, é representado por a+. a+ é, exatamente, "a*.a", evitando que a cadeia nula venha a aparecer nessa linguagem.