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.