LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES SIMULADO 2 ESTÁCIO

Prévia do material em texto

1a
          Questão
	Acerto: 1,0  / 1,0
	
	A análise sintática é usualmente implementada a partir de uma gramática:
		
	
	Sensível ao contexto
	 
	Livre de contexto
	
	Regular
	
	Irrestrita
	
	Com estrutura de frase
	
	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.
	
		2a
          Questão
	Acerto: 1,0  / 1,0
	
	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
	
	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)+
	
		3a
          Questão
	Acerto: 1,0  / 1,0
	
	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 ∩ B) ∩ C tem no máximo 2 elementos
	
	A ∩ B tem no máximo 1 elemento
	
	A ∩ ∅ tem 3 elementos pelo menos
	
	(A ∪ B) ∪ C tem no máximo 2 elementos
	
	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.
	
		4a
          Questão
	Acerto: 1,0  / 1,0
	
	(POSCOMP / 2016) O autômato finito exposto abaixo representa qual expressão regular?
		
	
	(bb + d)* (aa + c)*
	 
	a*b(c + da*b)*
	
	a*b (d* + cb)
	
	a*c* (b +d)*
	
	ab*(da* + cb)*
	
	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)*.
	
		5a
          Questão
	Acerto: 1,0  / 1,0
	
	A expressão regular que permite reconhecer a digitação correta de CEP no Brasil no modelo ddddd-ddd é:
		
	 
	^\\d{5,5}\\-\\d{3,3}$
	
	^\\d{3,5}\\-\\d{5,3}$
	
	^\\d{3,3}\\-\\d{5,5}$
	
	^\\d{5,1}\\-\\d{3,1}$
	
	^\\d{5,5}\\-\\d{3,1}$
	
	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}$"
	
		6a
          Questão
	Acerto: 1,0  / 1,0
	
	(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* )*
	
	( a | b )*
	
	( ( a  )* | b* )*
	 
	( b* a b* a b* )*
	
	(a b* b b*)*
	
	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'.
	
		7a
          Questão
	Acerto: 1,0  / 1,0
	
	(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:
		
	
	A gramática II é livre de contexto.
	
	A gramática III é livre de contexto.
	
	Nenhuma das gramáticas é livre de contexto.
	
	A gramática I é livre de contexto.
	 
	A gramática IV é livre de contexto.
	
	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.
	
		8a
          Questão
	Acerto: 1,0  / 1,0
	
	Em relação a autômatos e linguagens, podemos afirmar:
I. PDA é o formato de máquina de linguagem livre de contexto.
II. A descrição instantânea do PDA descreve a configuração dele em uma determinada instância.
III. Uma cadeia de uma LLC pode ser aceita por pilha vazia ou pelo estado final.
É correto apenas o que se afirma em:
		
	
	II e III
	
	II
	 
	I, II e III
	
	I e III
	
	I
	
	Explicação:
Gabarito: I, II e III
Justificativa: Os autômatos de Pilha (PDA) são o formato de máquina de autômatos finitos para linguagens livres de contexto. A Descrição Instantânea descreve a configuração do PDA em uma determinada instância, onde o ID lembra as informações do estado e o conteúdo da pilha em uma determinada instância de tempo. Uma cadeia w (LLC) pode ser declarada aceita por uma pilha vazia se, após o processamento de todos os símbolos de w, a pilha estiver vazia. Uma cadeia w pode ser declarada aceita pelo estado final se, após a passagem total da cadeia w, o PDA entrar em um estado final.
	
		9a
          Questão
	Acerto: 1,0  / 1,0
	
	Analise as seguintes afirmativas
 
I. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão. Em um problema de localização, procura-se localizar uma certa estrutura que satisfaça um conjunto de propriedades dadas. Se as propriedades envolverem critérios de otimização, então o problema é dito de otimização.
II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-completos é aplicado somente para esse tipo de problema.
III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP podem ser resolvidos da mesma forma.
A análise permite concluir que:
		
	 
	As afirmativas I, II e III estão corretas.
	
	Apenas a afirmativa I está correta.
	
	Apenas as afirmativas I e II estão corretas.
	
	Apenas as afirmativas I e III estão corretas.
	
	Apenas a afirmativa II está correta.
	
	Explicação:
Em um problema de decisão, o objetivo é decidir a resposta sim ou não. Problemas de otimização envolvem critério de otimização. Afirmativa I está correta. Os problemas NP-Completos são objeto da teoria da complexidade computacional e são problemas de decisão que, até o momento, não foram reduzidos a um tempo de solução polinomial. A afirmativa II está correta. Para esse caso hipotético, por redução, implica que P=NP. Uma vez que P=NP, existem algoritmos polinomiais para todos os problemas NP e a proposição III é correta. Ocorre que não se sabe se P=NP, ainda.
	
		10a
          Questão
	Acerto: 1,0  / 1,0
	
	Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase sem qualquer restrição. Dentro dessa hierarquia estão classificadas a linguagem recursiva e a linguagem recursivamente enumerável.  Acerca de suas características assinale a afirmação verdadeira.
 
		
	 
	Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável.
	
	Uma linguagem recursiva e uma recursivamenteenumerável podem fazer um loop para sempre na entrada de uma máquina de Turing.
	
	Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
	
	Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva.
	
	Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
	
	Explicação:
As linguagens recursivas estão contidas no conjunto das linguagens recursivamente enumeráveis. Portanto, não são equivalentes. Uma linguagem recursiva é uma linguagem aceita por uma Máquina de Turing. Ambas as linguagens são aceitas por Máquinas de Turing. Quando uma linguagem é rejeitada a MT para, não entra em loop infinito.