Teoria da Computação: Gramáticas e Linguagens

Prévia do material em texto

04/06/2020 EPS
simulado.estacio.br/alunos/ 1/3
 
 
 
 TEORIA DA COMPUTAÇÃO
9a aula
 Lupa 
PPT MP3
 
Exercício: CCT0832_EX_A9_201908040459_V1 19/05/2020
Aluno(a): JOSEILDON DA SILVA DANTAS 2020.1 EAD
Disciplina: CCT0832 - TEORIA DA COMPUTAÇÃO 201908040459
 
 1a 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
Respondido em 19/05/2020 08:52:11
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.
 
 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
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
Um símbolo especial escolhido aparte de V denominado inicial
Respondido em 19/05/2020 08:52: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.
http://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:abre_frame('2','9','','','');
javascript:abre_frame('3','9','','','');
04/06/2020 EPS
simulado.estacio.br/alunos/ 2/3
 
 3a 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
 I.
II e IV.
 II.
I e III.
III e IV.
 
Respondido em 19/05/2020 08:52:16
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.)
 
 4a 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 sem categorização possível e que gera a coleção das palíndromas em {0,1} exclusivamente de tamanho
par.
 
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 regular. 
Respondido em 19/05/2020 08:52:19
Explicação:
04/06/2020 EPS
simulado.estacio.br/alunos/ 3/3
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
 
 5a 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 cadeia aabbb é gerada por essa gramática.
a gramática G é ambígua.
 é possível encontrar uma gramática regular equivalente a G.
a gramática G gera a cadeia nula.. 
a gramática G é uma gramática livre de contexto.
Respondido em 19/05/2020 08:52:44
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)
 
 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
 
Um símbolo especial escolhido aparte de V denominado inicial
Conjunto finito de símbolos ou variáveis Não-Terminais
 Regras de produção da forma
Conjunto finito de símbolos terminais DISJUNTOS
Respondido em 19/05/2020 08:52:47
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','194141063','3876732791');