EXERCICIO 4

Prévia do material em texto

03492 - LINGUAGENS REGULARES
	 
		
	
		1.
		(POSCOMP / 2013) Sobre o Lema do Bombeamento (pumping lemma) para linguagens regulares, considere as afirmativas a seguir.
 
I. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L1 = {w ∈ Σ* | w termina com b} não é regular.
II. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que a linguagem L2 = {(an)2 | n ≥ 1} não é regular.
III. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do Bombeamento, que as linguagens L3 = {an! | n ≥ 1}, L4 = {anbamban+m | n, m ≥ 1} e L5 = {am+1bn+1 | 2 ≤ n ≤ m ≤ 3n} não são regulares.
IV. Se a linguagem for do tipo 3, então aplica-se o Bombeamento.
 
Assinale a alternativa correta.
	
	
	
	Somente as afirmativas III e IV são corretas.
	
	
	Somente as afirmativas I, II e III são corretas.
	
	
	Somente as afirmativas II, III e IV são corretas.
	
	
	Somente as afirmativas I e IV são corretas.
	
	
	Somente as afirmativas I e II são corretas.
	Data Resp.: 04/12/2023 17:45:33
		Explicação: 
Gabarito: Somente as afirmativas II, III e IV são corretas.
Justificativa: vamos aplicar o lema do bombeamento no item I. w é qualquer cadeia de 'a' e 'b' que termina em b. Seja a cadeia w = abaab. Vamos dividir essa em três: x = 'a', y = 'ba' e z = 'ab'. Claramente o nosso comprimento de bombeamento é y = 2 ('ba') e p = 5. Assim vamos satisfazer as condições do lema:
1. |y| ≥ 1
2. |xy| ≤ p
3. para todo i ≥ 0, xyiz ∈ L
y é a subcadeia que pode ser bombeada (removida ou repetida arbitrariamente).
Removendo y temos a cadeia aab que pertence a L1. Repetindo y duas vezes temos a cadeia ababaab que pertence a L1, uma vez que pertence a Σ* e termina em 'b'. É fácil perceber que a repetição de y dentro de w vai continuar satisfazendo a condição de pertencer a Σ* e terminar em 'b'. Portanto, não foi possível provar que L1 não é regular. Como o lema foi satisfeito para L1, então L pode ou não ser regular. Nada se pode afirmar e a afirmativa I é falsa. Todas as outras são verdadeiras
	
	
	 
		
	
		2.
		Com base nas afirmativas abaixo assinale a resposta correta:
I.  As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos finitos.
II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0.
III. Em todo autômato finito existe sempre um estado inicial fixo.
IV. Gramáticas têm um número finito de regras de produção.
	
	
	
	II e IV, apenas
	
	
	II e III, apenas
	
	
	I, II e IV, apenas
	
	
	I, III e IV, apenas
	
	
	I e IV, apenas.
	Data Resp.: 04/12/2023 17:46:04
		Explicação: 
Gabarito: I, III e IV, apenas
Justificativa: As linguagens regulares são as do tipo 3 e não do tipo 0. As demais alternativas estão corretas.
	
	
	 
		
	
		3.
		Dado que A = {x ∊ ℕ | 1 < x < 3} e B = {x ∊ ℕ | 2 < x < 20}, então A ∩ B =
	
	
	
	{ }
	
	
	{3,4}
	
	
	{2}
	
	
	{3}
	
	
	{2,3}
	Data Resp.: 04/12/2023 17:46:30
		Explicação: 
Gabarito: { }
Justificativa: O conjunto A = {2} e o conjunto B = {3..19}. Logo a intersecção de ambos é vazia, uma vez que não há elementos comuns entre A e B
	
	
	 
		
	
		4.
		Analise as seguintes afirmativas.
I. Um Autômato Finito fornece o modelo mais simples de um dispositivo de computação.
II. A principal utilidade da teoria dos autômatos está no projeto do computador.
III. Um AF é um modelo matemático usado para representar programas de computador.
A análise permite concluir que
	
	
	
	Somente as afirmativas II e III são falsas.
	
	
	Somente a afirmativa I é falsa.
	
	
	Somente a afirmativa II é falsa.
	
	
	Somente as afirmativas I e II são falsas.
	
	
	Somente a afirmativa III é falsa.
	Data Resp.: 04/12/2023 17:47:04
		Explicação: 
Gabarito: Somente a afirmativa II é falsa.
Justificativa: A principal utilidade da teoria dos autômatos está no projeto do compilador.
	
	
	 
		
	
		5.
		A expressão regular que permite reconhecer a digitação correta de CPF no Brasil é:
	
	
	
	^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
	
	
	\\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2}
	
	
	^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{3}$
	
	
	^\\d{3}\\.\\d{3}\\.\\d{3}\\.\\d{2}$
	
	
	^\\d{3}\\-\\d{3}\\-\\d{3}\\-\\d{2}$
	Data Resp.: 04/12/2023 17:48:19
		Explicação: 
Gabarito: ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
Justificativa: Sabemos que a expressão deverá iniciar com 3 dígitos separados por um ponto: ^\\d{3}\\. Devemos repetir três vezes esse padrão, colocar o separador "-", e mais dois dígitos verificadores. Lembrando que o '^' marca o início e o '$' o final da expressão regular. Assim, a expressão regular em Java para CPF será:
^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$
	
	
	 
		
	
		6.
		A expressão regular que permite reconhecer a digitação correta de CEP no Brasil no modelo ddddd-ddd é:
	
	
	
	^\\d{3,5}\\-\\d{5,3}$
	
	
	^\\d{5,1}\\-\\d{3,1}$
	
	
	^\\d{3,3}\\-\\d{5,5}$
	
	
	^\\d{5,5}\\-\\d{3,3}$
	
	
	^\\d{5,5}\\-\\d{3,1}$
	Data Resp.: 04/12/2023 17:49:10
		Explicação: 
Gabarito: ^\\d{5,5}\\-\\d{3,3}$
Justificativa: O padrão de CEP no Brasil é composto de 5 dígitos numéricos separados por um traço e mais três dígitos. A única alternativa que satisfaz esse padrão é a alternativa "^\\d{5,5}\\-\\d{3,3}$"
	
	
	 
		
	
		7.
		Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta?
	
	
	
	S ∩ ∅ = S
	
	
	S U ∅ = ∅
	
	
	S U ∅ = S - ∅ = S
	
	
	S U ∅ = S - ∅ = ∅
	
	
	S - ∅ = ∅
	Data Resp.: 04/12/2023 17:50:48
		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.
	
	
	 
		
	
		8.
		(POSCOMP / 2008) Considere o autômato finito mostrado na figura abaixo (os círculos em negrito representam estados terminais)
A esse respeito, assinale a afirmativa FALSA.
	
	
	
	A palavra ababa não é reconhecida pelo autômato.
	
	
	A palavra aba é reconhecida pelo autômato.
	
	
	A palavra baba é reconhecida pelo autômato.
	
	
	A palavra vazia é reconhecida pelo autômato.
	
	
	A palavra aaa é reconhecida pelo autômato.
	Data Resp.: 04/12/2023 17:50:56
		Explicação: 
Gabarito: A palavra aba é reconhecida pelo autômato.
Justificativa: Esse AFN realiza uma transição em ε para um estado final, logo reconhece a palavra vazia. Essa mesma transição permite o reconhecimento de baba. Existe um caminho para o reconhecimento de aaa e ababa não é reconhecida. Logo, todas essas alternativas são verdadeiras.  A palavra aba não é reconhecida pelo autômato porque não há caminhos que levem a um estado final. Essa alternativa é falsa.
	
	
	 
		
	
		9.
		(POSCOMP / 2009 - adaptada) Seja o alfabeto Σ={a,b}
e a linguagem regular L={ω|ω∈Σ∗e on°de a's emωé par}
		. Qual das expressões regulares abaixo gera essa linguagem?
	
	
	
	( b* | ( a )* | b* )*
	
	
	( a | b )*
	
	
	(a b* b b*)* 
	
	
	( b* a b* a b* )*
	
	
	( ( a  )* | b* )*
	Data Resp.: 04/12/2023 17:51:27
		Explicação: 
Gabarito: ( b* a b* a b* )*
Justificativa: Observe que a única alternativa em que se pode garantir que haverá a ocorrência de zero ou outro número par de 'a' é ( b* a b* a b* )*. Nas demais alternativas, sempre é possível gerar uma palavra com número ímpar de 'a'.
	
	
	 
		
	
		10.
		(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
	
	
	
	Gramática irrestrita.
	
	
	Gramática regular.
	
	
	Gramática livre de contexto.
	
	
	Gramática sensível ao contexto.
	
	
	Gramática de pilha.
	Data Resp.: 04/12/2023 17:51:57
		Explicação: 
Gabarito: Gramática regular.
Justificativa: A primeira fase do compilador chamada analisador léxico é projetada pelos autômatos finitos, que são os reconhecedores das expressões regularesgeradas pelas gramáticas regulares.