EXERCICIO 6

Prévia do material em texto

03493 - LINGUAGENS LIVRES DE CONTEXTO
	 
		
	
		1.
		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:
	
	
	
	I e III
	
	
	I, II e III
	
	
	II e III
	
	
	I
	
	
	II
	Data Resp.: 04/12/2023 18:06:54
		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.
	
	
	 
		
	
		2.
		Pilhas possuem somente uma entrada chamada de topo e são compostas por duas operações fundamentais. Sobre os conceitos de pilha, como é implementado os mecanismos de inserção/remoção:
	
	
	
	FIFA.
	
	
	PEPS.
	
	
	LIFO.
	
	
	FIFO.
	
	
	FFLL.
	Data Resp.: 04/12/2023 18:07:41
		Explicação: 
Gabarito: LIFO.
Justificativa: Uma pilha é uma estrutura de dados baseado no princípio de Last In First Out (LIFO).
	
	
	 
		
	
		3.
		A Forma Normal de Chomsky é um outro tipo de forma normal, além da BNF. Qual das seguintes produções está em CNF (NT = Não Terminal)?
	
	
	
	(NT) → (Cadeia de exatamente três terminais)
	
	
	(NT) → (Cadeia de exatamente quatro terminais)
	
	
	(NT) → (Cadeia de cinco ou mais NT)
	
	
	(NT) → (Cadeia de exatamente dois NT)
	
	
	(NT) → (Cadeia de um terminal e três não terminais)
	Data Resp.: 04/12/2023 18:08:27
		Explicação: 
Gabarito: (NT) → (Cadeia de exatamente dois NT)
Justificativa: A forma normal CNF é aquela em que o número de símbolos à direita de uma produção é estritamente limitado. Em particular, a cadeia à direita de uma produção consiste em não mais que dois símbolos.
	
	
	 
		
	
		4.
		Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC, é denominada de:
	
	
	
	Sem contexto.
	
	
	Finita.
	
	
	Recursiva.
	
	
	Infinita.
	
	
	Irrestrita (sem restrições).
	Data Resp.: 04/12/2023 18:08:52
		Explicação: 
Gabarito: Finita.
Justificativa: Uma linguagem L gerada a partir de uma dada GLC é finita se não houver ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC.
	
	
	 
		
	
		5.
		Alguns tipos de símbolos e produções aumentam o número de etapas na geração de uma linguagem a partir de uma GLC. Nesse sentido, símbolos inúteis em uma Gramática Livre de Contexto são:
	
	
	
	Alfabetos nulos.
	
	
	Símbolos não terminais.
	
	
	Cadeia nula.
	
	
	Símbolos não geradores e símbolos não alcançáveis.
	
	
	Produções nulas.
	Data Resp.: 04/12/2023 18:09:19
		Explicação: 
Gabarito: Símbolos não geradores e símbolos não alcançáveis.
Justificativa: Os dois tipos de símbolos inúteis incluem os símbolos não geradores, aqueles símbolos que não produzem nenhuma cadeia terminal, e os símbolos não alcançáveis, aqueles símbolos que não podem ser alcançados a qualquer momento a partir do símbolo inicial. Toda linguagem livre de contexto pode ser gerada por uma gramática livre de contexto em que não há símbolos inacessíveis ou inúteis.
	
	
	 
		
	
		6.
		Considere as seguintes produções da gramática da linguagem C e assinale a opção que não está em BNF:
	
	
	
	< inclusive-or-expression > ::= < exclusive-or-expression >
                            | < inclusive-or-expression > |  < exclusive-or-expression >
	
	
	< conditional-expression > ::= < logical-or-expression >
                           | < logical-or-expression > ? < expression > : < conditional-expression >
	
	
	< logical-and-expression > ::= < inclusive-or-expression >
                           | < logical-and-expression > && < inclusive-or-expression >
	
	
	< and-expression > ::= < equality-expression >
                   | < and-expression > & < equality-expression >
	
	
	< logical-or-expression > →
                          | < logical-or-expression > || < logical-and-expression >
	Data Resp.: 04/12/2023 18:11:07
		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 ::=
	
	
	 
		
	
		7.
		Qual é a linguagem gerada pela gramática S → aSb, S → A, A → aA
	
	
	
	∅
	
	
	ambm
	
	
	ambn
	
	
	anbm
	
	
	ajbi
	Data Resp.: 04/12/2023 18:11:35
		Explicação: 
Gabarito: ∅
Justificativa: As regras de produção não geram uma cadeia composta apenas de símbolos terminais. Portanto, a linguagem gerada é vazia.
	
	
	 
		
	
		8.
		O que é verdadeiro para a seguinte GLC?
S → aA | λ
A → bA | a
	
	
	
	A produção nula não pode ser removida.
	
	
	Como A não produz λ, λ pode ser removido.
	
	
	Como S produz λ, λ pode ser removido.
	
	
	Como A não produz λ, λ não pode ser removido.
	
	
	A produção nula pode ser removida.
	Data Resp.: 04/12/2023 18:12:05
		Explicação: 
Gabarito: A produção nula não pode ser removida.
Justificativa: Se S pode ser derivado em λ, então a produção nula não pode ser removida.
	
	
	 
		
	
		9.
		A diferença entre autômatos finitos e autômatos de pilha está na:
	
	
	
	Pilha.
	
	
	Fita de entrada.
	
	
	Controle finito.
	
	
	Cabeça de leitura.
	
	
	Direção do movimento da cabeça de leitura.
	Data Resp.: 04/12/2023 18:12:38
		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.
	
	
	 
		
	
		10.
		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:
	
	
	
	V, V, V, V, F.
	
	
	F, V, F, V, V.
	
	
	V, V, F, V, F.
	
	
	V, F, V, F, F.
	
	
	F, V, V, F, V.
	Data Resp.: 04/12/2023 18:12:44
		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.