Baixe o app para aproveitar ainda mais
Prévia do material em texto
• Pergunta 1 1 em 1 pontos Leia o excerto a seguir: “Quanto às estruturas das gramáticas regulares, é possível perceber nas gramáticas lineares uma forte restrição no formato das produções, no caso, o lado esquerdo possui exatamente uma variável, já o lado direito de uma produção é constituído por, no máximo, uma variável. Adicionalmente, essa variável, se existir, sempre antecede (linear à esquerda) ou sucede (linear à direita) qualquer subpalavra”. DIVERIO, T. M.; MENEZES, P. B. Teoria da computação : máquinas universais e computabilidade. Porto Alegre: Grupo A, 2011. p. 110. Sobre as propriedades das gramáticas regulares, analise as afirmativas a seguir. I. Existe mais de uma maneira de restringir as regras de produção das linguagens, de forma a definir uma gramática regular. II. Podemos ter nas formas de estruturação das gramáticas regulares: gramáticas lineares à direita e gramáticas regulares à esquerda. III. A gramática linear unitária à direita é o único tipo possível de produção unitária das gramáticas lineares. IV. Por definição, seja G = (V, T, P, S) uma gramática. A linguagem gerada pela gramática G será L(G), tal que: L(G) = { w ∈ T* ⏐ S ⇒+ w }. Está correto o que se afirma em: Resposta Selecionada: I, II e IV, apenas. Resposta Correta: I, II e IV, apenas. Comentário da resposta: Resposta correta. A alternativa está correta, porque temos mais de uma forma de restrição quanto às regras de produção de linguagens no tocante às gramáticas regulares; logo, podemos, sim, ter tanto estruturas de gramáticas lineares à direita e à esquerda, por definição estrutural de qualquer gramática regular, dado G = (V, T, P, S) sendo uma gramática. A linguagem gerada pela gramática G será L(G), tal que: L(G) = { w ∈ T* ⏐ S ⇒+ w }. • Pergunta 2 1 em 1 pontos Leia o excerto a seguir: “As gramáticas de grafos têm duas ideias fundamentais em suas estruturas. São elas: as regras de produção quanto aos pares de grafos, e a regra da derivação, que visa à substituição de um subgrafo de acordo com as regras de produção das linguagens, o que, por sua vez, orienta a estrutura da hierarquia de Chomsky, conforme o tipo de linguagem a ser gerada”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 169. A partir do exposto, analise as asserções a seguir e a relação proposta entre elas. I. As gramáticas de grafos constituem um caso particular das gramáticas categóricas. Pois: II. A ideia básica consiste em substituir palavras por grafos de acordo com o conceito de gramática de Chomsky. A seguir, assinale a alternativa correta. Resposta Selecionada: As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. Resposta Correta: As asserções I e II são proposições verdadeiras, e a II é uma justificativa correta da I. Comentário da resposta: Resposta correta. A alternativa está correta, pois a asserção I é uma proposição verdadeira, já que as gramáticas de grafos são reflexos do caso particular da classificação de gramáticas categóricas. Essa é a definição proposta pela gramática de Chomsky. A asserção II também é uma proposição verdadeira e justifica a I, porque as gramáticas de grafos são um caso específico das gramáticas categóricas; logo, a elaboração delas consiste em substituir palavras por grafos, conforme o conceito de gramática de Chomsky. Dessa forma, a definição presente da gramática de Chomsky limita as categorias, criando o caso específico da gramática de grafos como uma situação singular das gramáticas categóricas. • Pergunta 3 1 em 1 pontos Observe a figura a seguir, que apresenta uma ilustração das Expressões Regulares (ER) e dos seus autômatos correspondentes a zero operadores, ou seja, temos expressões regulares à esquerda, e os seus respectivos autômatos finitos a partir de zero operadores à direita: MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. Fonte: Menezes (2015, p. 125). #PraCegoVer : na ilustração, temos expressões regulares e seus respectivos autômatos finitos a partir de zero operadores. Na coluna à esquerda, temos as expressões regulares e, na coluna à direita, temos os autômatos finitos correspondentes. Temos, na coluna à esquerda, as respectivas expressões regulares, a partir de r com zero operadores; na primeira linha após o título, é apresentado r = ∅; na segunda linha, temos r=ε e, na terceira linha, temos r = x (x pertencente a Σ). Respectivamente, na coluna à direita, contendo os autômatos finitos correspondentes às expressões regulares, temos, na primeira linha, M1 = (∅, { q0 }, δ1, q0, ∅), M2 = (∅, { qf }, δ2, qf, { qf }) e M3 = ({ x }, { q0, qf }, δ3, q0, { qf }). Considerando a figura ilustrada, a fim de apresentar o esquema lógico das expressões regulares e autômatos, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) Em uma linguagem formal, as expressões são responsáveis pelo encadeamento lógico do comportamento da linguagem. II. ( ) Nas linguagens formais, as operações vão derivar dos respectivos autômatos finitos correspondentes e das gramáticas regulares. III. ( ) A expressão regular (bb) é responsável por concatenar a linguagem gerada contendo somente a palavra b. IV. ( ) A expressão regular (ab*) é responsável por concatenar a linguagem gerada com todas as palavras que iniciam com a. Assinale a alternativa que apresenta a sequência correta. Resposta Selecionada: V, V, F, V. Resposta Correta: V, V, F, V. Comentário da resposta: Resposta correta. A alternativa está correta, pois em uma linguagem formal, as expressões regulares têm por finalidade gerar o encadeamento lógico do comportamento da linguagem. Logo, nas linguagens formais, as operações vão derivar dos respectivos autômatos finitos e de suas gramáticas regulares correspondentes. Considerando que a expressão regular (ab*) é responsável por concatenar a linguagem por ela gerada, teremos como produto todas as palavras que iniciam com (a). • Pergunta 4 1 em 1 pontos Leia o excerto a seguir: “As linguagens de programação são tratadas adequadamente na hierarquia de Chomsky. Existem linguagens que não são livres do contexto, para as quais o poder dos formalismos sensíveis ao contexto é excessivo, sendo inadequados, principalmente no que se refere à complexidade”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 145. A respeito da teoria das estruturas hierárquicas de Chomsky e de sua aplicabilidade quanto às linguagens, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) As gramáticas livres de contexto ou tipo 2 apresentam como desafios as múltiplas ocorrências de um mesmo trecho de programa. II. ( ) As gramáticas sensíveis ao contexto ou tipo 1 apresentam a associação de um significado (semântica) a partir do código de um programa. III. ( ) O estudo da classe das linguagens livres do contexto permite uma representação simples da sintaxe tanto para linguagens artificiais como para linguagens naturais. IV. ( ) As gramáticas de grafos têm como ideia fundamental: regras de produção ímpares, formadas por grafos. Assinale a alternativa que apresenta a sequência correta. Resposta Selecionada: V, V, V, F. Resposta Correta: V, V, V, F. Comentário da resposta: Resposta correta. A alternativa está correta. De fato, as gramáticas livres de contexto ou tipo 2 apresentam como desafios as múltiplas ocorrências de um mesmo trecho de programa. Essas são características das gramáticas livres de contexto ou tipo 2. Já as gramáticas sensíveis ao contexto ou tipo 1 apresentam a associação de um significado (semântica) a partir do código de um programa. Pordefinição, esse é o comportamento esperado delas. Logo, o estudo da classe das linguagens livres do contexto permite uma representac ̧ão simples da sintaxe tanto para linguagens artificiais como para linguagens naturais. • Pergunta 5 1 em 1 pontos Leia o excerto a seguir: “A classificação das gramáticas, segundo a hierarquia de Chomsky, começa pelo tipo 0, com maior nível de liberdade em suas regras, e aumenta as restrições até o tipo 3. Cada nível é um super conjunto do próximo. Logo, uma gramática de tipo n é, consequentemente, uma linguagem de tipo n - 1”. DIVERIO, T. M.; MENEZES, P. B. Teoria da computação : máquinas universais e computabilidade. Porto Alegre: Grupo A, 2011. p. 121. Sobre os níveis de aplicabilidade da hierarquia de Chomsky, analise as afirmativas a seguir. I. Na classificação da hierarquia de Chomsky, o tipo 0 se refere às gramáticas com estrutura de fase, que apresentam maior nível de liberdade nas suas regras. II. Na classificação da hierarquia de Chomsky, o tipo 2 se refere às gramáticas livres de contexto, que são empregadas na análise sintática da teoria da computação. III. Na classificação da hierarquia de Chomsky, o tipo 3 se refere às gramáticas regulares, que são empregadas na análise léxica da teoria da computação. IV. Na classificação da hierarquia de Chomsky, o tipo 1 se refere às gramáticas sensíveis à semântica, que são empregadas nas linguagens de programação. Está correto o que se afirma em: Resposta Selecionada: I, II e III, apenas. Resposta Correta: I, II e III, apenas. Comentário da resposta: Resposta correta. A alternativa está correta, porque, na hierarquia de Chomsky, o tipo 0 se refere às gramáticas com estrutura de fase ou recursivamente enumeráveis que, por sua vez, apresentam maior nível de liberdade. Quanto às classificações, o tipo 2 se refere às gramáticas livres de contexto e o tipo 3 remete às gramáticas regulares. O tipo 2 é empregado na análise sintática, enquanto o tipo 3 é empregado na análise léxica. • Pergunta 6 1 em 1 pontos Leia o excerto a seguir: “Na teoria da computação, é comum o emprego de autômatos finitos construídos a partir de gramáticas regulares, pois a própria elaboração de linguagens regulares permeia o emprego das gramáticas; logo, é importante perceber que a gramática é fundamental para implementação e construção do autômato finito”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 102. A respeito das gramáticas regulares e dos autômatos e de sua aplicabilidade nas expressões regulares, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) É possível haver uma gramática linear à esquerda e à direita, simultaneamente. II. ( ) Caso uma gramática seja linear à direita, a linguagem gerada será regular. III. ( ) Caso uma gramática seja linear à esquerda, a linguagem gerada não será regular. IV. ( ) Uma gramática regular não pode dar origem a um autômato finito não determinístico. Assinale a alternativa que apresenta a sequência correta. Resposta Selecionada: V, V, F, F. Resposta Correta: V, V, F, F. Comentário da resposta: Resposta correta. A alternativa está correta. A gramática pode, simultaneamente, ser linear à esquerda e linear à direita. De fato, caso a gramática seja linear à direita, teremos uma linguagem regular sendo gerada, por definição da teoria das gramáticas regulares; caso ocorra uma gramática linear à esquerda, também teríamos uma linguagem regular sendo gerada. Logo, podem haver gramáticas lineares tanto à esquerda quanto à direita. • Pergunta 7 1 em 1 pontos Leia o excerto a seguir: “As expressões regulares são consideradas adequadas para a comunicação humano com humano e, principalmente, para a comunicação humano com máquina, por meio de operações matemáticas e de propriedades de concatenação e união; logo, as expressões regulares sempre buscaram explicar matematicamente o funcionamento de uma linguagem, a partir da teoria dos conjuntos”. MENEZES, P. B. Linguagens formais e autômatos . São Paulo: Sagah, 2015. p. 96. Sobre as propriedades das expressões regulares, analise as afirmativas a seguir: I. Uma expressão regular vazia parte do pressuposto de haver uma linguagem vazia. II. Dada uma expressão regular, que deriva de uma linguagem regular vazia, a partir da inserção do elemento “x”, a linguagem não será mais vazia e terá como elemento único “x”. III. Dado (r) e (s) como expressões regulares, com as respectivas linguagens R e S, caso quiséssemos realizar a operação de união, teríamos a expressão: (r*s). IV. Dado (r) e (s) como expressões regulares, com as respectivas linguagens R e S, caso quiséssemos realizar a operação de concatenação, teríamos a expressão: (r+s). Está correto o que se afirma em: Resposta Selecionada: I e II, apenas. Resposta Correta: I e II, apenas. Comentário da resposta: Resposta correta. A alternativa está correta, porque uma expressão regular vazia deriva, necessariamente, de uma linguagem vazia; da mesma forma, uma dada expressão regular, que deriva de uma linguagem vazia, a partir do momento em que ocorre a inserção de um elemento “x”, não será mais vazia e terá como elemento único: “x”. Assim, quando temos uma linguagem vazia, a sua expressão regular será vazia, sem elementos. Desse modo, um elemento novo a ser inserido preencherá a linguagem; esta, por sua vez, não estará mais vazia. • Pergunta 8 1 em 1 pontos A teoria das linguagens formais foi desenvolvida com o intuito de aproximar as linguagens humanas, bem como a sua estruturação e formação, com as linguagens regulares e com o emprego dos autômatos, que têm, na sua base, as expressões e as gramáticas regulares. A partir do exposto, qual é a definição de expressões regulares? Resposta Selecionada: Um formalismo que expressa a construção de uma linguagem regular. Resposta Correta: Um formalismo que expressa a construção de uma linguagem regular. Comentário da resposta: Resposta correta. A alternativa está correta, pois a definição de expressões regulares visa a definir um formalismo denotacional, que pode ser considerado gerador, já que é provável inferir como construir, ou seja, gerar as palavras de uma linguagem regular. Dessa forma, uma expressão regular pode ser definida a partir de conjuntos básicos e operações de concatenação e de união, com o objetivo de construir uma linguagem regular. • Pergunta 9 1 em 1 pontos As gramáticas regulares são fundamentais para derivar formas estruturais que irão compor as linguagens regulares que serão criadas, ou seja, não cabe falar de linguagem regular sem gramática, tendo em vista que as regras que coordenam o encadeamento lógico das linguagens se derivam das gramáticas regulares. Diante do exposto, qual é a definição de gramática regular? Resposta Selecionada: Trata-se de restrições lógicas sobre a forma de produção de uma linguagem regular. Resposta Correta: Trata-se de restrições lógicas sobre a forma de produção de uma linguagem regular. Comentário da resposta: Resposta correta. A alternativa está correta, pois a definição de gramática regular abarca as restrições lógicas impostas no desenvolvimento e produção de uma linguagem regular; logo, o encadeamento lógico das linguagens se deriva das gramáticas regulares, que estruturam regras e restrições de funcionamento para a linguagem. • Pergunta 10 1 em 1 pontos Observe a figura na sequência, que apresenta a ilustração de um autômato finito construído a partir da gramática G, com três conexões, à direita, qf, à esquerda, S e, embaixo, B. Verifique, portanto, a respectiva ilustração quanto ao fluxo de conexões do autômato finito. MENEZES, P. B. Linguagensformais e autômatos . São Paulo: Sagah, 2015. Fonte: Menezes (2015, p. 102). #PraCegoVer : a figura apresenta um autômato finito construído a partir da gramática G, sendo M = ({ a, b }, { S, A, B, qf }, δ, S, { qf }), em que G = ({ S, A, B }, { a, b }, P, S). O respectivo autômato apresenta três conexões, à direita, qf, à esquerda, S e, embaixo, B. Essas conexões estão representadas por círculos: três círculos alinhados na horizontal e um círculo abaixo do círculo central com setas indicando justamente as conexões. Considerando a figura ilustrada, a fim de apresentar o funcionamento do teorema do bombeamento para linguagens regulares utilizando autômatos, analise as afirmativas a seguir e assinale V para a(s) Verdadeira(s) e F para a(s) Falsa(s). I. ( ) Caso o autômato reconheça uma entrada (S) de comprimento maior ou igual ao número de estados (n), obrigatoriamente, o autômato assumirá algum estado (q) mais de uma vez. II. ( ) Caso o autômato assuma algum estado (q) mais de uma vez, verificamos, então, que existe um ciclo na função programa que passa por (q); assim, o bombeamento é executado zero ou mais vezes. III. ( ) O teorema do bombeamento não garante que os formalismos regulares são capazes de expressar diversos tipos de bombeamento, por exemplo: duplo bombeamento ou triplo bombeamento. IV. ( ) O teorema do bombeamento é diferente do lema do bombeamento para linguagens regulares, pois este descreve as propriedades essenciais de todas as linguagens regulares. Assinale a alternativa que apresenta a sequência correta. Resposta Selecionada: V, V, F, F. Resposta Correta: V, V, F, F. Comentário da resposta: Resposta correta. A alternativa está correta. A afirmativa I é verdadeira, porque dada uma entrada (S) de comprimento maior ou igual ao número de estados (n), obrigatoriamente, por definição, teremos que o autômato assumirá algum estado (q) mais de uma vez. A afirmativa II também é verdadeira, pois, assumindo mais de uma vez algum estado (q), existirá um ciclo na função programa que passa por (q); logo, teremos o bombeamento executado zero ou mais vezes.
Compartilhar