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

Prévia do material em texto

1a
          Questão
	Acerto: 1,0  / 1,0
	
	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
		
	
	ab_
	
	_ab9
	
	7b1
	
	a0
	 
	ab_9
	
	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.
	
		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.
Qual a linguagem gerada pela gramática: G = {(S, A), (0, 1), (S→0S1, S→A, A→0A), S}.
		
	
	1m0m
	
	0m1n
	 
	λ
	
	1m0n
	
	0m1m
	
	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.
	
		3a
          Questão
	Acerto: 1,0  / 1,0
	
	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
	
	anc bn, onde n ≥ 0
	
	an c bm, onde n, m ≥ 1
	
	a+ b+ c
	
	ca+ b+
	
	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.
	
		4a
          Questão
	Acerto: 1,0  / 1,0
	
	(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
		
	 
	Gramática regular.
	
	Gramática livre de contexto.
	
	Gramática de pilha.
	
	Gramática irrestrita.
	
	Gramática sensível ao contexto.
	
	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 regulares geradas pelas gramáticas regulares.
	
		5a
          Questão
	Acerto: 1,0  / 1,0
	
	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.
		
	
	I, II e IV, apenas
	 
	I, III e IV, apenas
	
	I e IV, apenas.
	
	II e IV, apenas
	
	II e III, apenas
	
	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.
	
		6a
          Questão
	Acerto: 1,0  / 1,0
	
	(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 vazia é reconhecida pelo autômato.
	
	A palavra ababa não é reconhecida pelo autômato.
	
	A palavra baba é reconhecida pelo autômato.
	 
	A palavra aba é reconhecida pelo autômato.
	
	A palavra aaa é reconhecida pelo autômato.
	
	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.
	
		7a
          Questão
	Acerto: 1,0  / 1,0
	
	Considere as seguintes produções da gramática da linguagem C e assinale a opção que não está em BNF:
		
	
	< and-expression > ::= < equality-expression >
                   | < and-expression > & < equality-expression >
	 
	< logical-or-expression > →
                          | < logical-or-expression > || < logical-and-expression >
	
	< conditional-expression > ::= < logical-or-expression >
                           | < logical-or-expression > ? < expression > : < conditional-expression >
	
	< logical-and-expression > ::= < inclusive-or-expression >
                           | < logical-and-expression > && < inclusive-or-expression >
	
	< inclusive-or-expression > ::= < exclusive-or-expression >
                            | < inclusive-or-expression > |  < exclusive-or-expression >
	
	Explicação:
Gabarito:
< logical-or-expression > → < logical-and-expression >
                          | < logical-or-expression > || < logical-and-expression >
Justificativa: Não se usa → na BNF. A forma correta quando se utiliza BNF é a utilização do símbolo ::=
	
		8a
          Questão
	Acerto: 1,0  / 1,0
	
	Considere a seguinte propriedade sobre uma linguagem formal L: ¿Existe um número natural n ≥ 0, tal que para qualquer palavra w ∈ L:
1. Todo z ∈ L com z ≥ n pode ser escrito como w = uvwxy, para algumas cadeias u,v,w,x,y.
2. |vx| ≥ 1
3. |vwx| ≤ n
4. uvkwxky ∈ L para todo k ≥ 0
 
Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F (falso) para as afirmativas a seguir.
· (   ) Se L é aceita por PDA, então L satisfaz a propriedade acima.
· (   ) L = {0p; onde p é primo} não satisfaz a propriedade acima.
· (   ) A propriedade acima é falsa para a linguagem L = {WcWR | W ∈ (a, b)*}
· (   ) A linguagem {anbncn; n ≥ 0} não satisfaz a propriedade acima.
· (   ) O lema do bombeamento para linguagem livre de contexto é usado ​​para provar que certos conjuntos são livres de contexto.
Assinale a alternativa que contém, de cima para baixo, a sequência correta:
		
	
	F, V, V, F, V.
	
	V, F, V, F, F.
	 
	V, V, F, V, F.
	
	V, V, V, V, F.
	
	F, V, F, V, V.
	
	Explicação:
Gabarito: V, V, F, V, F.
Justificativa:
1. Esse é o lema do bombeamento para LLC e toda LLC é reconhecida por um PDA.
2. Aplicando o lema é possível provar que 0p não é livre de contexto e não satisfaz a propriedade.
3. WcWR é LLC, logo a propriedade é verdadeira e a afirmativa é falsa.
4. Está correta conforme pode ser lido no Módulo 4, núcleo conceitual 1.
5. O lema do bombeamento para linguagem livre de contexto é usado ​​para provar que certos conjuntos não são livres de contexto. Alternativa falsa.
	
		9a
          Questão
	Acerto: 1,0  / 1,0
	
	Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto finito de estados, Σ é o conjunto finito de alfabetos de entrada, Γ é o símbolo de fita permitido, L significa esquerda, R significa direita e Hsignifica parada).
		
	 
	Q × Γ → (Q × Γ × {L, R, H})
	
	Q × Γ → (Q × Σ × {H})
	
	Q × Γ → (Q × Σ)
	
	Q ×Σ→ (Q × Σ × {L, R, H})
	
	Q ×Σ→ (Q × {L, R, H})
	
	Explicação:
A função de transição de estados para MT é definida como um produto cartesiano de Q × Γ, onde Γ é alfabeto da fita, levando em uma imagem definida por outro produto cartesiano de Q × Γ multiplicado pelas ações da máquina em seguir para a esquerda, direita ou parar {L, R, H}.
	
		10a
          Questão
	Acerto: 1,0  / 1,0
	
	Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução do segundo problema possa ser usada para resolver o primeiro problema. Em particular, a redutibilidade pode ser usada para demonstrar que problemas são indecidíveis ou decidíveis. Nesse contexto, avalie as seguintes afirmativas:
I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução de A na presença de um método para resolver B.
II. Reduções apresentam um importante papel em classificar os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
 
Quais as afirmativas verdadeiras?
		
	
	I, II e III.
	
	II e III.
	 
	I e II.
	
	I e III.
	
	III.
	
	Explicação:
Na afirmativa III, se A é redutível a B e B é um problema indecidível, então A é um problema indecidível.