LINGUAGENS FORMAIS

Prévia do material em texto

LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES
	
		Lupa
	 
	Calc.
	
	
	 
	 
	 
	
	
	
	
		Disc.: LING FORMAIS E A 
	2022.2 (G) / EX
		Prezado (a) Aluno(a),
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se familiarizar com este modelo de questões que será usado na sua AV e AVS.
	03491CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS
	 
		
	
		1.
		A análise sintática é usualmente implementada a partir de uma gramática:
	
	
	
	Com estrutura de frase
	
	
	Livre de contexto
	
	
	Regular
	
	
	Irrestrita
	
	
	Sensível ao contexto
	Data Resp.: 12/09/2022 11:01:29
		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.
	
	
	 
		
	
		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 'b' virá primeiro
	
	
	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
	Data Resp.: 12/09/2022 11:02:05
		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.
		Sejam os conjuntos A com 2 elementos, B com 4 elementos, C com 5 elementos, então:
	
	
	
	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 tem no máximo 1 elemento
	
	
	(A ∪ B) ∪ C tem no máximo 2 elementos
	Data Resp.: 12/09/2022 11:02:13
		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.
	
	
	03492LINGUAGENS REGULARES
	 
		
	
		4.
		(POSCOMP / 2016) O autômato finito exposto abaixo representa qual expressão regular?
	
	
	
	a*b(c + da*b)*
	
	
	a*c* (b +d)*
	
	
	ab*(da* + cb)*
	
	
	a*b (d* + cb)
	
	
	(bb + d)* (aa + c)*
	Data Resp.: 12/09/2022 11:02:20
		Explicação:
Gabarito: a*b(c + da*b)*
Justificativa: Esse AF reconhece a*b, uma vez que essa cadeia leva a um estado final. Na sequência deve reconhecer qualquer número de entradas de 'c' e deixar o estado quando receber uma entrada 'd'. Permanecer nesse primeiro estado enquanto entrar 'a' e voltar ao estado final quando entrar um 'b'. Essa parte implica reconhecer c*+ da*b. Ocorre que para reconhecer apenas a cadeia a*b essa segunda parte tem que ser nula, daí a necessidade de se acrescentar um fecho de kleene na segunda expressão, resultando em: a*b(c + da*b)*.
	
	
	 
		
	
		5.
		A expressão regular que permite reconhecer a digitação correta de CEP no Brasil no modelo ddddd-ddd é:
	
	
	
	^\\d{3,3}\\-\\d{5,5}$
	
	
	^\\d{5,5}\\-\\d{3,3}$
	
	
	^\\d{3,5}\\-\\d{5,3}$
	
	
	^\\d{5,5}\\-\\d{3,1}$
	
	
	^\\d{5,1}\\-\\d{3,1}$
	Data Resp.: 12/09/2022 11:02:24
		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}$"
	
	
	 
		
	
		6.
		(POSCOMP / 2009 - adaptada) Seja o alfabeto Σ={a,b}Σ={a,b} e a linguagem regular L={ω|ω∈Σ∗e on°de a's emωé par}L={ω|ω∈Σ∗e on°de a's emωé par}. Qual das expressões regulares abaixo gera essa linguagem?
	
	
	
	( b* | ( a )* | b* )*
	
	
	( b* a b* a b* )*
	
	
	(a b* b b*)*
	
	
	( a | b )*
	
	
	( ( a  )* | b* )*
	Data Resp.: 12/09/2022 11:02:28
		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'.
	
	
	03493LINGUAGENS LIVRES DE CONTEXTO
	 
		
	
		7.
		A diferença entre autômatos finitos e autômatos de pilha está na:
	
	
	
	Fita de entrada.
	
	
	Pilha.
	
	
	Cabeça de leitura.
	
	
	Controle finito.
	
	
	Direção do movimento da cabeça de leitura.
	Data Resp.: 12/09/2022 11:02:34
		Explicação:
Gabarito: Pilha.
Justificativa: Os autômatos de Pilha são o formato de máquina de autômatos finitos para linguagens livres de contexto. É um autômato finito com a anexação de uma quantidade auxiliar de armazenamento chamada de pilha. A pilha é o componente do PDA que o diferencia dos autômatos finitos.
	
	
	 
		
	
		8.
		(POSCOMP / 2008) Considere as seguintes gramáticas:
	I
	II
	III
	IV
	A → bA
A → aA
A → ε
	B → BB
B → b
	C → CaC
A → AcA
A → aca
	D → EE
EE → FG
F → a | aF
G → b | bG
A esse respeito, assinale a afirmativa FALSA:
	
	
	
	Nenhuma das gramáticas é livre de contexto.
	
	
	A gramática I é livre de contexto.
	
	
	A gramática IV é livre de contexto.
	
	
	A gramática III é livre de contexto.
	
	
	A gramática II é livre de contexto.
	Data Resp.: 12/09/2022 11:02:38
		Explicação:
Gabarito: A gramática IV é livre de contexto.
Justificativa: As gramáticas livres de contexto devem ter produções da forma:
P = {A → β | A ∈ V ∧ β ∈ (V ∪ T)*}
Claramente, a gramática IV tem produções que não estão no formato das gramáticas livres de contexto. As demais gramáticas têm todas as produções neste formato.
	
	
	03494COMPUTABILIDADE E A MÁQUINA DE TURING
	 
		
	
		9.
		Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA.
	
	
	
	Todo problema que está na classe P também está na classe NP.
	
	
	Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente, X é redutível em tempo polinomial para qualquer outro problema Y na classe NP.
	
	
	Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente enumerável, então L é uma linguagem recursiva.
	
	
	Segundo a Tese de Church, a capacidade de computação representada pela máquina de Turing é o limite máximo que pode ser atingido por qualquer modelo de computação.
	
	
	A união de duas linguagens recursivas é uma linguagem recursiva.
	Data Resp.: 12/09/2022 11:02:43
		Explicação:
Um problema é NP completo quando está na classe NP, e todo problema NP completo conhecido pode ser reduzido a ele. O correto seria Y é redutível a X em tempo polinomial, porque, pela definição, todo problema NP-Completo poderia ser redutível a X. As demais alternativas estão corretas.
	
	
	 
		
	
		10.
		Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.
I. A descoberta do cientista implica P = NP.
PORQUE
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-Completos.
A respeito dessas asserções, assinale a opção correta.
	
	
	
	As asserções I e II são proposiçõesverdadeiras e a II é uma justificativa correta da I.
	
	
	As asserções I e II são proposições falsas.
	
	
	A asserção I é uma proposição verdadeira e a II é uma proposição verdadeira.
	
	
	A asserção I é uma proposição falsa e a II é uma proposição verdadeira.
	
	
	As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
	Data Resp.: 12/09/2022 11:02:52
		Explicação:
Sabemos que P ⊆ NP, ou seja, P é um subconjunto de NP. Problemas NP-completos são um conjunto de problemas que podem ser reduzidos em tempo polinomial a partir de qualquer outro problema NP, mas cuja solução ainda pode ser verificada em tempo polinomial. Um problema NP-completo é pelo menos tão difícil quanto qualquer outro problema NP. Para esse caso hipotético, por redução, implica que P=NP e a asserção I é verdadeira. Uma vez que P=NP, existem algoritmos polinomiais para todos os problemas NP e a proposição II é verdadeira e uma justificativa da I.