Salve - Aula 09 - Teoria da Computação - Teste de Conhecimento

Prévia do material em texto

TEORIA DA COMPUTAÇÃO
9a aula
 Lupa 
PPT MP3
 
 
 1a 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
 é 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.
a gramática G gera a cadeia nula.. 
a cadeia aabbb é gerada por essa gramática.
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)
 
 2a 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
Uma palavra ¿final¿, composta dos símbolos terminais
 
Regras de produção da forma
Conjunto finito de símbolos ou variáveis Não-Terminais
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. 
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:abre_frame('2','9','','','');
javascript:abre_frame('3','9','','','');
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.
 
 3a 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
Pilha
Autômatos infinitos
 Gramáticas livres-do-contexto
Autômatos finitos
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.
 
 4a 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
III e IV.
 
II e IV.
I e III.
I.
 II.
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.)
 
 5a 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 livre de contexto que não é gramática regular
Uma gramática sensível a contexto que não é gramática livre de contexto
 Uma 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.
 
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
 
 6a Questão
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
Uma palavra ¿final¿, composta dos símbolos terminais
 
Conjunto finito de símbolos ou variáveis Não-Terminais
 Regras de produção da forma
Conjunto finito de símbolos terminais DISJUNTOS
Um símbolo especial escolhido aparte de V denominado inicial
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.
javascript:abre_colabore('38403','194089431','3875684403');