Safari - 25 de out de 2023 2221

Disc.: LINGU A GENS FORMAIS, A UT ÔMA T OS E LINGU A GENS FORMAIS, A UT ÔMA T OS E COMPILADORES COMPILADORES ! ! ! ! Acertos: 1,0 1,0 de 2,0 de 2,0 15/09/2023 15/09/2023 Acerto: 0,2 0,2 ! / ! 0,2 0,2 Adaptado do livro Linz, Peter . An Introduction to F ormal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016. Qual o tipo da seguinte gramática: S \u2192 aSb ! e S \u2192 ab Com estrutura de fr ase Regular Irrestrito Sensível ao Conte xto Livre de Conte xto Respondido em 15/09/2023 21:18:18 Explicação: T odas as gramáticas do tipo 2, livres de conte xto, devem ter suas regras de produção atendendo às seguintes restrições: 1. T odas as regras de produção de vem ser do tipo (Não-terminal) \u2192 (T erminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho do não-terminal do lado esquerdo da produção dev e ser igual a 1, ou seja |Não-terminal| = 1. A gramática do enunciado atende a essas duas restrições. Acerto: 0,0 0,0 ! / ! 0,2 0,2 Dado que A = {x \u220a \u2115 | 1 \u220a \u2115 | 2 \u2229 B = {3} { } {2} {2,3} {3,4} Respondido em 15/09/2023 21:18:33 Explicação: Gabarito: Gabarito: { } Justi\ufb01cativa: Justi\ufb01cativa: O conjunto A = {2} e o conjunto B = {3..19}. L ogo a intersecção de ambos é vazia, uma vez que não há elementos comuns entre A e B Acerto: 0,0 0,0 ! / ! 0,2 0,2 Seja a seguinte gramática S \u2192 aSa | bSb | a | b P alíndromos são cadeias do tipo ww r , ou seja, aqueles que lidos da esquerda para a direita ou vice e v ersa, são iguais. A linguagem gerada pela gr amática acima sobre o alfabeto {a, b) é o conjunto de: T odos os palíndromos. !!! Cadeias que começam e terminam com símbolos diferentes. T odos os palíndromos de comprimento ímpar . A gramática não ger a palíndromos. T odos os palíndromos de comprimento par . Respondido em 15/09/2023 21:18:48 Explicação: Gabarito: Gabarito: T odos os palíndromos de comprimento ímpar . Justi\ufb01cativa: ! Justi\ufb01cativa: ! Realizando algumas derivações como e xemplo pode-se perceber que a alternativa b é a correta, por e xemplo: S \u2192 aSa \u2192 S \u2192 aaa; S \u2192 aSa \u2192 S \u2192 abSba \u2192 ababa. Acerto: 0,2 0,2 ! / ! 0,2 0,2 Um cientista a\ufb01rma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P . Considerando que esta a\ufb01rmação tem implicações importantes no que diz respeito à comple xidade computacional, avalie as seguintes asserções e a relação proposta entre elas. I. A descoberta do cientista implica P = NP . POR QUE II. A descoberta do cientista implica na e xistência de algoritmos polinomiais para todos os problemas NP-Completos. A respeito dessas asserções, assinale a opção correta. As asserções I e II são proposições verdadeir as, mas a II não é uma justi\ufb01cativa correta da I. A asserção I é uma proposição falsa e a II é uma proposição verdadeir a. As asserções I e II são proposições falsas. A asserção I é uma proposição verdadeir a e a II é uma proposição verdadeir a. As asserções I e II são proposições verdadeir as e a II é uma justi\ufb01cativa correta da I. Respondido em 15/09/2023 21:19:06 Explicação: Sabemos que P \u2286 NP , ou seja, P é um subconjunto de NP . Problemas NP-completos são um conjunto de problemas que podem ser reduzidos em tempo polinomial a partir de qualquer outro problema NP , mas cuja solução ainda pode ser veri\ufb01cada em tempo polinomial. Um problema NP-completo é pelo menos tão difícil quanto qualquer outro problema NP . Par a esse caso hipotético, por redução, implica que P=NP e a asserção I é verdadeir a. Uma vez que P=NP , existem algoritmos polinomiais para todos os problemas NP e a proposição II é v erdadeira e uma justi\ufb01cativa da I. Acerto: 0,0 0,0 ! / ! 0,2 0,2 Considere, a seguir , a gramática livre de conte xto G = (V , T , P , S), onde V = {S}, T = {a,b,c}, e P: S \u2192 aS|Sb|c Qual e xpressão regular gera a mesma linguagem que a gramática de\ufb01nida acima? ca+ b+ an c bm, onde n, m \u2265 0 a+ b+ c anc bn, onde n \u2265 0 an c bm, onde n, m \u2265 1 Respondido em 15/09/2023 21:19:27 Explicação: Aplicando algumas regras de produção podemos inferir a lei ger al de formação de cadeias dessa linguagem. S \u2192 c. Isso equivale a \u03bb c \u03bb . Logo n, m \u2265 0, eliminamos as alternativas de a) até c), uma v ez que pode hav er cadeias sem símbolos ¿a¿ e/ ou ¿b¿. Sejam os e xemplos: S \u2192 aS \udb8b\udc1b ac e S \u2192 Sb \udb8b\udc1b cb. Esses dois e x emplos nos mostram que as cadeias dessa linguagem podem ter números diferentes de símbolos ¿a¿ e ¿b¿, indicando que a alternativa d está errada. Acerto: 0,2 0,2 ! / ! 0,2 0,2 (POSCOMP / ! 2008 - adaptada) Analise as seguintes igualdades de e xpressões regulares: I. a * = (a)* II. (a+b)* = (b+a)* III. a *+b * = (a+b)* A análise permite concluir que somente a igualdade III é verdadeir a. somente a igualdade I é verdadeir a. somente as igualdades II e III são verdadeir as. somente as igualdades I e II são verdadeir as. somente a igualdade II é verdadeir a. Respondido em 15/09/2023 21:22:14 Explicação: Gabarito: Gabarito: somente as igualdades I e II são verdadeir as. Justi\ufb01cativa: Justi\ufb01cativa: a * + b * signi\ufb01ca qualquer combinação de 'a ' ou qualquer combinação de 'b ' , ou seja, as cadeias são formadas apenas por ' a' ou por 'b ' . (a + b)* consiste em qualquer combinação de ' a' e 'b ' , ou seja, as cadeias podem conter os símbolos 'a ' e 'b ' em sua formação, logo a alternativa III é falsa. A alternativa II é verdadeir a porque segundo o fecho de Kleene podemos considerar \u03a3 = {a, b } e \u03a3 * de\ufb01nido como o conjunto de todas as cadeias, incluindo a cadeia nula, portanto as linguagens são iguais e geradas por e xpressões equivalentes. A alternativa I é, claramente, v erdadeira, bastando retir ar os parênteses da e xpressão à direita. Acerto: 0,2 0,2 ! / ! 0,2 0,2 Gramáticas de\ufb01nem linguagens, sendo especi\ufb01cações \ufb01nitas de regras de ger ação de cadeias. ! Nesse sentido, assinale a alternativa incorreta. \u03bb \u2208 \u03a3 * a + b denota {a} U {b} = {a, b } V \u2229 T = \u03a3 * V U T = \u03a3 V \u2229 T = \u2205 Respondido em 15/09/2023 21:23:03 Explicação: Gabarito: Gabarito: V \u2229 T = \u03a3 * Justi\ufb01cativa: Justi\ufb01cativa: Observe que V é o conjunto dos não terminais e T é o conjunto dos terminais. São dois conjuntos disjuntos, logo sua intersecção é vazia. T odas as demais alternativas estão corretas. Acerto: 0,2 0,2 ! / ! 0,2 0,2 Existem dois tipos principais de complexidade computacional para um algoritmo: comple xidade de tempo e complexidade do espaço. Nesse sentido, o que é falso para o problema da classe P? É computáv el por uma máquina de T uring determinística em tempo polinomial. Ele contém todos os conjuntos nos quais a pertinência pode ser decidida por um algoritmo cujo tempo de e xecução é limitado por um polinômio. O número de passos (ou tempo ) necessários para completar o algoritmo é uma função polinomial de n. Em geral, a classe P contém todos os problemas que são resolvidos facilmente usando computadores. P é de\ufb01nido como o conjunto de todos os problemas de decisão para os quais e xiste um algoritmo que pode ser realizado por uma máquina de T uring não- determinística em tempo polinomial. Respondido em 15/09/2023 21:23:24 Explicação: P é de\ufb01nido como o conjunto de todos os problemas de decisão para os quais e xiste um algoritmo que pode ser realizado por uma máquina de T uring determinística determinística em tempo polinomial. Acerto: 0,0 0,0 ! / ! 0,2 0,2 Adaptado do livro Linz, Peter . An Introduction to F ormal Languages and Automata, 6. Ed. Jones & Bartlett Learning, 2016. Qual a linguagem gerada pela gr amática: G = {(S, A), (0, 1), (S \u2192 0S1, S \u2192 A, A \u2192 0A), S}. 1 m 0 m \u03bb 0 m1m 0 m 1 n 1 m 0 n Respondido em 15/09/2023 21:23:47 Explicação: Observe que não e xiste uma regra de produção que possa nos levar a um símbolo terminal apenas. T odas as regras de produção, se aplicadas, nos levam a cadeias compostas de terminais e não terminais. Sendo impossível ger ar cadeias formadas apenas de terminais, essa é uma linguagem vazia. Acerto: 0,0 0,0 ! / ! 0,2 0,2 (POSCOMP / ! 2008) ! Considere o autômato \ufb01nito mostrado na \ufb01gura abaix o ( os círculos em negrito representam estados terminais) A esse respeito, assinale a a\ufb01rmativa F ALSA. A palavr a aba é reconhecida pelo autômato. A palavr a baba é reconhecida pelo autômato. A palavr a aaa é reconhecida pelo autômato. A palavr a vazia é reconhecida pelo autômato. A palavr a ababa não é reconhecida pelo autômato. Respondido em 15/09/2023 21:24:10 Explicação: Gabarito: Gabarito: A palavr a aba é reconhecida pelo autômato. Justi\ufb01cativa: Justi\ufb01cativa: Esse AFN realiza uma tr ansição em \u03b5 para um estado \ufb01nal, logo reconhece a palavr a vazia. Essa mesma transição permite o reconhecimento de baba. ! Existe um caminho para o reconhecimento de aaa e ababa não é reconhecida. Logo, todas essas alternativas são verdadeir as. ! A palavra aba não é reconhecida pelo autômato porque não há caminhos que lev em a um estado \ufb01nal. Essa alternativa é falsa. Questão 1 1 a Questão 2 2 a Questão 3 3 a Questão 4 4 a Questão 5 5 a Questão 6 6 a Questão 7 7 a Questão 8 8 a Questão 9 9 a Questão 10 10 a 25 /10/2023 22 : 21 P á gi na 1 de 1

Safari - 25 de out de 2023 2221

Linguagens Formais, Autômatos e Computabilidade

ESTÁCIO

Faça como milhares de estudantes: teste grátis o Passei Direto

Agora você pode testar o

Passei Direto grátis

Linguagens Formais, Autômatos e Computabilidade

Continue navegando

Outros materiais