exe3automatos

Prévia do material em texto

<p>Você acertou 4 de 10</p><p>questões</p><p>Verifique o seu desempenho e continue</p><p>treinando! Você pode refazer o exercício</p><p>quantas vezes quiser.</p><p>Verificar Desempenho</p><p>A</p><p>B</p><p>C</p><p>1 Marcar para revisão</p><p>Em relação a autômatos e linguagens, podemos</p><p>afirmar:</p><p>I. PDA é o formato de máquina de linguagem</p><p>livre de contexto.</p><p>II. A descrição instantânea do PDA descreve a</p><p>configuração dele em uma determinada</p><p>instância.</p><p>III. Uma cadeia de uma LLC pode ser aceita por</p><p>pilha vazia ou pelo estado final.</p><p>É correto apenas o que se afirma em:</p><p>I</p><p>II</p><p>I e III</p><p>Questão 1 de 10</p><p>Corretas �4�</p><p>Incorretas �6�</p><p>Em branco �0�</p><p>1 2 3 4 5</p><p>6 7 8 9 10</p><p>Exercicio</p><p>Linguagens Livres De</p><p>Contexto</p><p>Sair</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 1/14</p><p>D</p><p>E</p><p>II e III</p><p>I, II e III</p><p>Resposta incorreta</p><p>Opa! A alternativa correta é a letra</p><p>E. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>Gabarito: I, II e III</p><p>Justificativa: Os Autômatos de Pilha �PDA)</p><p>são a representação de máquinas de</p><p>autômatos finitos para linguagens livres de</p><p>contexto. A Descrição Instantânea é uma</p><p>ferramenta que descreve a configuração</p><p>do PDA em um determinado momento,</p><p>armazenando informações sobre o estado</p><p>atual e o conteúdo da pilha. Uma cadeia de</p><p>uma Linguagem Livre de Contexto �LLC)</p><p>pode ser considerada aceita de duas</p><p>formas: pela pilha vazia, se após o</p><p>processamento de todos os símbolos da</p><p>cadeia, a pilha estiver vazia; ou pelo estado</p><p>final, se após o processamento completo</p><p>da cadeia, o PDA alcançar um estado final.</p><p>Portanto, todas as afirmações estão</p><p>corretas.</p><p>2 Marcar para revisão</p><p>A diferença entre autômatos finitos e autômatos</p><p>de pilha está na:</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 2/14</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Cabeça de leitura.</p><p>Fita de entrada.</p><p>Controle finito.</p><p>Pilha.</p><p>Direção do movimento da cabeça de</p><p>leitura.</p><p>Resposta incorreta</p><p>Opa! A alternativa correta é a letra</p><p>D. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>A alternativa correta é a letra D, que indica</p><p>a "Pilha". A principal diferença entre</p><p>autômatos finitos e autômatos de pilha é a</p><p>presença de uma pilha no último. Os</p><p>autômatos de pilha, também conhecidos</p><p>como PDAs �Pushdown Automata), são</p><p>uma extensão dos autômatos finitos e são</p><p>usados para representar linguagens livres</p><p>de contexto. A pilha funciona como uma</p><p>memória auxiliar, permitindo que o</p><p>autômato de pilha reconheça padrões de</p><p>linguagem mais complexos do que os</p><p>autômatos finitos. Portanto, a pilha é o</p><p>elemento que distingue os autômatos de</p><p>pilha dos autômatos finitos.</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 3/14</p><p>A</p><p>B</p><p>C</p><p>3 Marcar para revisão</p><p>Considere a seguinte propriedade sobre uma</p><p>linguagem formal L� Existe um número natural n</p><p>≥ 0, tal que para qualquer palavra w ∈ L�</p><p>1. Todo z ∈ L com z ≥ n pode ser escrito como w</p><p>= uvwxy, para algumas cadeias u,v,w,x,y.</p><p>2. |vx| ≥ 1</p><p>3. |vwx| ≤ n</p><p>4. uvkwxky ∈ L para todo k ≥ 0</p><p>Com base no enunciado e nos conhecimentos</p><p>sobre o tema, atribua V (verdadeiro) ou F (falso)</p><p>para as afirmativas a seguir.</p><p>(   ) Se L é aceita por PDA, então L satisfaz</p><p>a propriedade acima.</p><p>(   ) L = �0 ; onde p é primo} não satisfaz a</p><p>propriedade acima.</p><p>(    ) A propriedade acima é falsa para a</p><p>linguagem L = �WcW | W ∈ (a, b)*}</p><p>(    ) A linguagem {a b c ; n ≥ 0} não</p><p>satisfaz a propriedade acima.</p><p>(    ) O lema do bombeamento para</p><p>linguagem livre de contexto é usado para</p><p>provar que certos conjuntos são livres de</p><p>contexto.</p><p>Assinale a alternativa que contém, de cima para</p><p>baixo, a sequência correta:</p><p>p</p><p>R</p><p>n n n</p><p>V, V, V, V, F.</p><p>V, V, F, V, F.</p><p>V, F, V, F, F.</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 4/14</p><p>D</p><p>E</p><p>F, V, V, F, V.</p><p>F, V, F, V, V.</p><p>Resposta correta</p><p>Parabéns, você selecionou a</p><p>alternativa correta. Confira o</p><p>gabarito comentado!</p><p>Gabarito Comentado</p><p>Gabarito: V, V, F, V, F.</p><p>Justificativa:</p><p>1. A primeira afirmação é verdadeira porque</p><p>o lema do bombeamento para linguagens</p><p>livres de contexto �LLC) afirma que toda</p><p>LLC é reconhecida por um Autômato com</p><p>Pilha Determinístico �PDA�.</p><p>2. A segunda afirmação é verdadeira</p><p>porque, ao aplicar o lema do</p><p>bombeamento, é possível provar que a</p><p>linguagem 0 , onde p é um número primo,</p><p>não é livre de contexto e, portanto, não</p><p>satisfaz a propriedade.</p><p>3. A terceira afirmação é falsa porque a</p><p>linguagem WcW , onde W ∈ (a, b)*, é uma</p><p>linguagem livre de contexto, logo a</p><p>propriedade é verdadeira.</p><p>4. A quarta afirmação é verdadeira,</p><p>conforme pode ser verificado no Módulo 4,</p><p>núcleo conceitual 1.</p><p>5. A quinta afirmação é falsa porque o lema</p><p>do bombeamento para linguagem livre de</p><p>contexto é usado para provar que certos</p><p>conjuntos não são livres de contexto, e não</p><p>o contrário.</p><p>p</p><p>R</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 5/14</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>4 Marcar para revisão</p><p>Alguns tipos de símbolos e produções</p><p>aumentam o número de etapas na geração de</p><p>uma linguagem a partir de uma Gramática Livre</p><p>de Contexto �GLC�. Nesse sentido, símbolos</p><p>inúteis em uma Gramática Livre de Contexto</p><p>são:</p><p>Símbolos não geradores e símbolos</p><p>não alcançáveis.</p><p>Alfabetos nulos.</p><p>Cadeia nula.</p><p>Símbolos não terminais.</p><p>Produções nulas.</p><p>Resposta correta</p><p>Parabéns, você selecionou a</p><p>alternativa correta. Confira o</p><p>gabarito comentado!</p><p>Gabarito Comentado</p><p>Os símbolos inúteis em uma Gramática</p><p>Livre de Contexto �GLC) são os símbolos</p><p>não geradores e os símbolos não</p><p>alcançáveis. Os símbolos não geradores</p><p>são aqueles que não produzem nenhuma</p><p>cadeia terminal, ou seja, não contribuem</p><p>para a formação de palavras na linguagem.</p><p>Por outro lado, os símbolos não</p><p>alcançáveis são aqueles que,</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 6/14</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>independentemente das regras de</p><p>produção aplicadas, nunca podem ser</p><p>derivados a partir do símbolo inicial.</p><p>Portanto, esses símbolos não têm utilidade</p><p>na geração de palavras na linguagem. É</p><p>importante ressaltar que toda linguagem</p><p>livre de contexto pode ser gerada por uma</p><p>gramática livre de contexto na qual não</p><p>existem símbolos inacessíveis ou inúteis.</p><p>5 Marcar para revisão</p><p>Uma linguagem L gerada a partir de uma dada</p><p>GLC onde não existem ciclos no grafo</p><p>direcionado gerado a partir das regras de</p><p>produção dessa GLC, é denominada de:</p><p>Infinita.</p><p>Irrestrita (sem restrições).</p><p>Sem contexto.</p><p>Finita.</p><p>Recursiva.</p><p>Resposta incorreta</p><p>Opa! A alternativa correta é a letra</p><p>D. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 7/14</p><p>A</p><p>B</p><p>C</p><p>Gabarito: Finita.</p><p>Justificativa: A linguagem L, gerada a</p><p>partir de uma dada Gramática Livre de</p><p>Contexto �GLC�, é classificada como finita</p><p>quando não existem ciclos no grafo</p><p>direcionado gerado a partir das regras de</p><p>produção dessa GLC. Isso significa que a</p><p>linguagem tem um número limitado de</p><p>sentenças que podem ser geradas, pois</p><p>não há ciclos que permitam a produção de</p><p>sentenças infinitas.</p><p>6 Marcar para revisão</p><p>Considere as seguintes produções da</p><p>gramática da linguagem C e assinale a opção</p><p>que não está em BNF�</p><p>::=</p><p>| ?</p><p>expression > :</p><p>→</p><p>| ||</p><p>::=</p><p>| &&</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 8/14</p><p>D</p><p>E</p><p>::=</p><p>| |</p><p>::=</p><p>| &</p><p>Resposta correta</p><p>Parabéns, você selecionou a</p><p>alternativa correta. Confira o</p><p>gabarito comentado!</p><p>Gabarito Comentado</p><p>Gabarito:</p><p>→</p><p>|</p><p>||</p><p>Justificativa: A alternativa B não está em</p><p>BNF �Backus-Naur Form), uma</p><p>metassintaxe usada para expressar</p><p>gramáticas livres de contexto. Na BNF, a</p><p>forma correta de representar uma</p><p>produção é utilizando o símbolo ::=, e não o</p><p>símbolo → como apresentado na</p><p>alternativa B. Portanto, a alternativa B é a</p><p>única que não segue a forma correta da</p><p>BNF.</p><p>7 Marcar para revisão</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 9/14</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Qual é a linguagem gerada pela gramática S →</p><p>aSb, S → A, A → aA?</p><p>a bm m</p><p>a bm n</p><p>∅</p><p>a bn m</p><p>a bj i</p><p>Resposta incorreta</p><p>Opa! A alternativa correta é a letra</p><p>C. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>A linguagem gerada pela gramática S →</p><p>aSb, S → A, A → aA é vazia, representada</p><p>pelo símbolo ∅. Isso ocorre porque as</p><p>regras de produção não conseguem gerar</p><p>uma cadeia composta apenas de símbolos</p><p>terminais. Em outras palavras, não é</p><p>possível formar uma sequência de</p><p>símbolos que não possa ser mais reduzida</p><p>através das regras de produção da</p><p>gramática. Portanto, a linguagem gerada é</p><p>vazia.</p><p>8 Marcar para revisão</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 10/14</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>Gramáticas definem linguagens, sendo</p><p>especificações finitas de regras de geração de</p><p>cadeias. Nesse sentido, assinale a alternativa</p><p>incorreta.</p><p>V ∩ T = ∅</p><p>V U T = Σ</p><p>λ ∈ Σ*</p><p>a + b denota {a} U {b} = {a, b}</p><p>V ∩ T = Σ*</p><p>Resposta incorreta</p><p>Opa! A alternativa correta é a letra</p><p>E. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>O gabarito é a alternativa E� V ∩ T = Σ*.</p><p>Para entender a justificativa, é importante</p><p>lembrar que V é o conjunto dos não</p><p>terminais e T é o conjunto dos terminais.</p><p>Estes são dois conjuntos disjuntos, ou seja,</p><p>não possuem elementos em comum.</p><p>Portanto, a intersecção entre eles �V ∩ T) é</p><p>um conjunto vazio, não sendo igual a Σ*. As</p><p>demais alternativas estão corretas, pois</p><p>seguem as regras de geração de cadeias</p><p>em gramáticas.</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 11/14</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>9 Marcar para revisão</p><p>Pilhas possuem somente uma entrada chamada</p><p>de topo e são compostas por duas operações</p><p>fundamentais. Sobre os conceitos de pilha,</p><p>como é implementado os mecanismos de</p><p>inserção/remoção?</p><p>FIFO.</p><p>FIFA.</p><p>LIFO.</p><p>FFLL.</p><p>PEPS.</p><p>Resposta incorreta</p><p>Opa! A alternativa correta é a letra</p><p>C. Confira o gabarito comentado!</p><p>Gabarito Comentado</p><p>O conceito de pilha é implementado</p><p>através do mecanismo conhecido como</p><p>LIFO �Last In, First Out), que em português</p><p>significa "último a entrar, primeiro a sair".</p><p>Isso significa que o último elemento que foi</p><p>inserido na pilha será o primeiro a ser</p><p>removido. Portanto, a alternativa correta é</p><p>a letra C, que apresenta o termo LIFO.</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 12/14</p><p>A</p><p>B</p><p>C</p><p>D</p><p>E</p><p>10 Marcar para revisão</p><p>Seja a seguinte gramática S → aSa | bSb | a | b</p><p>Palíndromos são cadeias do tipo ww , ou seja,</p><p>aqueles que lidos da esquerda para a direita ou</p><p>vice e versa, são iguais. A linguagem gerada</p><p>pela gramática acima sobre o alfabeto {a, b} é o</p><p>conjunto de:</p><p>r</p><p>Todos os palíndromos.</p><p>Todos os palíndromos de</p><p>comprimento ímpar.</p><p>Cadeias que começam e terminam</p><p>com símbolos diferentes.</p><p>Todos os palíndromos de</p><p>comprimento par.</p><p>A gramática não gera palíndromos.</p><p>Resposta correta</p><p>Parabéns, você selecionou a</p><p>alternativa correta. Confira o</p><p>gabarito comentado!</p><p>Gabarito Comentado</p><p>Gabarito: Todos os palíndromos de</p><p>comprimento ímpar.</p><p>Justificativa: A gramática apresentada</p><p>gera palíndromos de comprimento ímpar.</p><p>Isso pode ser observado ao realizar</p><p>algumas derivações como exemplo. Por</p><p>exemplo, se começarmos com S e</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 13/14</p><p>aplicarmos as regras da gramática,</p><p>podemos obter as seguintes cadeias: S →</p><p>aSa → aaa; S → aSa → abSba → ababa.</p><p>Ambas as cadeias são palíndromos de</p><p>comprimento ímpar, o que confirma que a</p><p>alternativa B é a correta.</p><p>09/10/2024, 11:18 estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/</p><p>https://estacio.saladeavaliacoes.com.br/exercicio/670690a4e945e4f14b86e31d/gabarito/ 14/14</p>