CCT0832 - Teste de conhecimento - Aula 9

Prévia do material em texto

1
        Questão
	
	
	Em uma gramática sensível ao contexto definida por  G = {V, T, P, S} o P significa?
		
	
	Um símbolo especial escolhido aparte de V denominado inicial
	 
	Regras de produção da forma
	
	Uma palavra ¿final¿, composta dos símbolos terminais
 
	
	Conjunto finito de símbolos ou variáveis Não-Terminais
	
	Conjunto finito de símbolos terminais DISJUNTOS
	Respondido em 15/03/2021 17:18:13
	
Explicação:
V - Conjunto finito de símbolos ou variáveis Não-Terminais, ou seja, são variáveis a serem substituídas por outras variáveis ou símbolos terminais nos passos de produção das palavras da gramática e nenhum deles deverá aparecer nas palavras finais da linguagem gerada por ela. 
T -Conjunto finito de símbolos terminais DISJUNTOS , ou seja, que não façam parte de V.  Eles são ditos ¿terminais¿ pois são os que farão parte das palavras geradas por essa gramática.
P - Regras de produção da forma:  
S - Um símbolo especial escolhido aparte de V denominado inicial. Este é o símbolo por onde começamos a substituição das regras de produção.
	
	
	 
		2
        Questão
	
	
	Considere a gramática G definida pelas regras de produção abaixo, em que os símbolos não-terminais são S, A e B, e os símbolos terminais são a e b. 
S -> AB
AB -> AAB
A -> a
B -> b
Com relação a essa gramática, é correto afirmar que
		
	
	a gramática G gera a cadeia nula.. 
	
	a cadeia aabbb é gerada por essa gramática.
	 
	é possível encontrar uma gramática regular equivalente a G.
	
	a gramática G é ambígua.
	
	a gramática G é uma gramática livre de contexto.
	Respondido em 15/03/2021 17:19:36
	
Explicação:
Quanto ao tipo da gramática, ela não é livre de contexto (alternativa B), pois uma das regras, a segunda, tem dois símbolos do lado esquerdo. 
As alternativas C e E estão incorretas porque nem a sentença nula, nem a sentença aabbb têm o formato aa*b (note que as sentenças da linguagem têm exatamente um b)
	
	
	 
		3
        Questão
	
	
	Um método mais poderoso de descrever linguagens que podem descrever certas características que têm uma estrutura recursiva o que as torna úteis em uma variedade de aplicações. O texto refere-se a:
		
	
	Expressões regulares
	
	Autômatos finitos
	
	Autômatos infinitos
	 
	Gramáticas livres-do-contexto
	
	Pilha
	Respondido em 15/03/2021 17:20:38
	
Explicação:
Conforme visto na aula 9, o ponto principal das gramáticas sensíveis ao contexto é que suas regras de produção não são independentes de uma pré-existência de condições da palavra que está sendo reconhecida.
	
	
	 
		4
        Questão
	
	
	Considere a gramática a seguir, em que S, A e B são símbolos não terminais, 0 e 1 são terminais e ε é a cadeia vazia.
S-> 1S|0A|ε
A-> 1S|0B|ε
B-> 1S|ε
A respeito dessa gramática, analise as afirmações a seguir.
I. Nas cadeias geradas por essa gramática, o último símbolo é 1.
II. O número de zeros consecutivos nas cadeias geradas pela gramática é, no máximo, dois.
III. O número de uns em cada cadeia gerada pela gramática é maior que o número de zeros.
IV. Nas cadeias geradas por essa gramática, todos os uns estão à esquerda de todos os zeros.
É correto apenas o que se afirma em
		
	 
	II.
	
	II e IV.
	
	I.
	
	I e III.
	
	III e IV.
 
	Respondido em 15/03/2021 17:22:15
	
Explicação:
 É uma questão de fácil resolução a partir da correta aplicação das regras de derivação da gramática para a construção de palavras.
A técnica a ser utilizada para a justificativa de uma alternativa como falsa é a apresentação de um contraexemplo de sequência de derivações que demonstre a falsidade.
A afirmativa I deve ser considerada falsa. O contraexemplo é a geração da palavra-vazia a partir do símbolo inicial S (nota do autor: essa é uma suposição, já que a questão pode ser considerada mal construída já que não informa qual dos símbolos, S, A ou B, é o símbolo inicial).
S => e (aplicação da regra S->e)
A afirmativa II é verdadeira. Considere a seguinte sequência de derivações, na qual W representa uma cadeia de símbolos terminais. A derivação demonstra as duas únicas regras que podem ser aplicadas a qualquer momento para remover o símbolo terminal B da palavra sendo gerada, de forma que número de zeros consecutivos será sempre no máximo dois.
S =>* W0A
 => W00B (Aplicação da regra S->0B é a única que gera zeros seguidos.)
 => W001S (Aplicação da regra B->1S.)
 ou
 => W00 (Aplicação da regra B->e.)
A afirmativa III é trivialmente falsa, já que a palavra-vazia pertence ao conjunto de palavras da linguagem gerada pela gramática apresentada. Ou seja, a quantidade zero de símbolos uns e zeros torna a afirmativa falsa. A seguinte sequência de derivações é o contraexemplo que justifica a afirmativa.
S => e (aplicação da regra S->e)
A afirmativa IV deve ser considerada falsa, pois é possível gerar a palavra 01 (na qual uns aparecem à direita de zeros) a partir da seguinte sequência de derivações do contraexemplo.
S => 0A (Aplicação da regra S->0A.)
S => 01S (Aplicação da regra A->1S.)
S => 01 (Aplicação da regra S->e.)
	
	
	 
		5
        Questão
	
	
	A gramática dada pelos descritores abaixo é:
G=
N={S,A}
T={0,1} e P é o conjunto de produções
{S → 0S 1A 01ε e A → 0S 1A 0}
		
	 
	Uma gramática regular. 
	
	Uma gramática sensível a contexto que não é gramática livre de contexto
	
	Uma gramática livre de contexto que não é gramática regular
	
	Uma gramática do tipo 0 que não é gramática sensível a contexto.
	
	Uma gramática sem categorização possível e que gera a coleção das palíndromas em {0,1} exclusivamente de tamanho par.
 
	Respondido em 15/03/2021 17:24:43
	
Explicação:
Pela forma das produções, sabe-se que a gramática é regular já que apresenta produções com cadeia de tamanho 1 à esquerda que podem ser substituídas por cadeias exclusivamente do tipo A→α onde onde α é constituída por um terminal ou por um terminal seguido de um não terminal.
Sabe-se também que existe uma hierarquia onde as gramáticas se incluem de modo que uma G0 inclui as GSC´s que por sua vez incluem as GLC´s e estas incluem como tipo especial as gramáticas regulares. Assim, se as regras satisfazem as condições do tipo mais interior, a opção correta é a letra D
	
	
	 
		6
        Questão
	
	
	Em uma gramática sensível ao contexto definida por  G = {V, T, P, S} o que  T significa?
		
	 
	Conjunto finito de símbolos terminais DISJUNTOS
	
	Um símbolo especial escolhido aparte de V denominado inicial
	
	Conjunto finito de símbolos ou variáveis Não-Terminais
	
	Uma palavra ¿final¿, composta dos símbolos terminais
 
	
	Regras de produção da forma
	Respondido em 15/03/2021 17:25:04
	
Explicação:
V - Conjunto finito de símbolos ou variáveis Não-Terminais, ou seja, são variáveis a serem substituídas por outras variáveis ou símbolos terminais nos passos de produção das palavras da gramática e nenhum deles deverá aparecer nas palavras finais da linguagem gerada por ela. 
T -Conjunto finito de símbolos terminais DISJUNTOS , ou seja, que não façam parte de V.  Eles são ditos ¿terminais¿ pois são os que farão parte das palavras geradas por essa gramática.
P - Regras de produção da forma:  
S - Um símbolo especial escolhido aparte de V denominado inicial. Este é o símbolo por onde começamos a substituição das regras de produção.