Teoria da Computação - TESTE 9

Prévia do material em texto

04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 1/3
Teste de
Conhecimento
 avalie sua aprendizagem
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:
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o P significa?
TEORIA DA COMPUTAÇÃO 
Lupa Calc.
 
 
CCT0832_A9_202008191076_V1 
Aluno: YURI CID DA SILVA LIMA Matr.: 202008191076
Disc.: TEORIA DA COMPUTAÇÃO 2021.1 EAD (G) / EX
Prezado (a) Aluno(a),
 
Você fará agora seu TESTE DE CONHECIMENTO! Lembre-se que este exercício é opcional, mas não valerá ponto para sua
avaliação. O mesmo será composto de questões de múltipla escolha.
Após responde cada questão, você terá acesso ao gabarito comentado e/ou à explicação da mesma. Aproveite para se
familiarizar com este modelo de questões que será usado na sua AV e AVS.
 
1.
Autômatos finitos
Gramáticas livres-do-contexto
Autômatos infinitos
Expressões regulares
Pilha
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.
 
 
2.
Uma palavra ¿final¿, composta dos símbolos terminais
 
Um símbolo especial escolhido aparte de V denominado inicial
Regras de produção da forma
Conjunto finito de símbolos ou variáveis Não-Terminais
Conjunto finito de símbolos terminais DISJUNTOS
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:voltar();
javascript:voltar();
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 2/3
Em uma gramática sensível ao contexto definida por G = {V, T, P, S} o que T significa?
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 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}
 
3.
Regras de produção da forma
Um símbolo especial escolhido aparte de V denominado inicial
Conjunto finito de símbolos ou variáveis Não-Terminais
Conjunto finito de símbolos terminais DISJUNTOS
Uma palavra ¿final¿, composta dos símbolos 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. 
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.
 
 
4.
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.
é possível encontrar uma gramática regular equivalente a G.
a gramática G é ambígua.
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)
 
 
5.
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. 
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
04/05/2021 Estácio: Alunos
https://simulado.estacio.br/alunos/?p0=33848280&user_cod=3070659&matr_integracao=202008191076 3/3
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
 
 
6.
III e IV.
 
II e IV.
I.
I e III.
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.)
 
 Não Respondida Não Gravada Gravada
 
 
Exercício inciado em 04/05/2021 12:51:59. 
 
 
 
 
javascript:abre_colabore('34697','224399775','4540049207');