Prévia do material em texto
Meus Simulados Teste seu conhecimento acumulado Disc.: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES Aluno(a): LUCAS ANDRADE VASCONCELOS 202001588787 Acertos: 5,0 de 10,0 19/11/2022 Acerto: 1,0 / 1,0 Considere uma cadeia "A" de tamanho 5. O número de subcadeias de A que podem ser geradas é: 64 32 10 16 5 Respondido em 19/11/2022 17:03:40 Explicação: Como sabemos, o número de subconjuntos de um conjunto com n elementos é igual a 2n. Assim, o número de subcadeias de uma cadeia de tamanho 5 será igual a 25 = 32 Acerto: 1,0 / 1,0 BIO-RIO - 2014 - ETAM - Curso de Formação de Técnicos - 2º Semestre Dados três conjuntos, A = {1,2,3}, B = {4,5} e C = {1,2,4}, observe os pares ordenados apresentados graficamente na figura abaixo. Esses pares correspondem, graficamente, a: B X (A U C) B X (A ∩ C) Questão1 a Questão2 a https://simulado.estacio.br/alunos/inicio.asp javascript:voltar(); (A ∩ C) X B C X (A U B) (A U C) X B Respondido em 19/11/2022 17:04:15 Explicação: A fim de que o produto cartesiano de B com qualquer outro conjunto fosse representado, os pares ordenados devem, necessariamente, iniciar com os elementos do conjunto B = {4, 5}. Como os pares da figura começam com os elementos 1 e 2, as alternativas a e d estão incorretas. A alternativa ¿e¿ nos obrigaria a ter um par ordenado começando com elemento 4. A intersecção dos conjuntos A e C contém os elementos comuns {1, 2}, uma vez que 3 não está contido em C. O produto cartesiano desse conjunto intersecção com o conjunto B é: {(1, 4); (1, 5); (2, 4); (2, 5)} Acerto: 1,0 / 1,0 Câmara Municipal de Marabá- Engenheiro Civil - FADESP-2021 A função exponencial y = ax+1 é tal que a imagem de 2 é 27. A imagem de 4 será: 729 64 81 243 256 Respondido em 19/11/2022 17:04:39 Explicação: Quando x = 2, ax+1 é igual a a3. O número que elevado ao cubo gera 27 é 3. Logo a função é: y = 3x+1 e a imagem de 4 será: 243 = 35 Acerto: 1,0 / 1,0 (POSCOMP / 2016) O autômato finito exposto abaixo representa qual expressão regular? a*b (d* + cb) ab*(da* + cb)* (bb + d)* (aa + c)* a*c* (b +d)* a*b(c + da*b)* Respondido em 19/11/2022 17:15:49 Explicação: Gabarito: a*b(c + da*b)* Questão3 a Questão4 a Justificativa: Esse AF reconhece a*b, uma vez que essa cadeia leva a um estado final. Na sequência deve reconhecer qualquer número de entradas de 'c' e deixar o estado quando receber uma entrada 'd'. Permanecer nesse primeiro estado enquanto entrar 'a' e voltar ao estado final quando entrar um 'b'. Essa parte implica reconhecer c*+ da*b. Ocorre que para reconhecer apenas a cadeia a*b essa segunda parte tem que ser nula, daí a necessidade de se acrescentar um fecho de kleene na segunda expressão, resultando em: a*b(c + da*b)*. Acerto: 0,0 / 1,0 A expressão regular que permite reconhecer a digitação correta de CEP no Brasil no modelo ddddd-ddd é: ^\\d{3,3}\\-\\d{5,5}$ ^\\d{5,5}\\-\\d{3,3}$ ^\\d{5,5}\\-\\d{3,1}$ ^\\d{3,5}\\-\\d{5,3}$ ^\\d{5,1}\\-\\d{3,1}$ Respondido em 19/11/2022 17:24:41 Explicação: Gabarito: ^\\d{5,5}\\-\\d{3,3}$ Justificativa: O padrão de CEP no Brasil é composto de 5 dígitos numéricos separados por um traço e mais três dígitos. A única alternativa que satisfaz esse padrão é a alternativa "^\\d{5,5}\\-\\d{3,3}$" Acerto: 0,0 / 1,0 (POSCOMP / 2009 - adaptada) Seja o alfabeto e a linguagem regular . Qual das expressões regulares abaixo gera essa linguagem? ( a | b )* ( b* a b* a b* )* ( b* | ( a )* | b* )* ( ( a )* | b* )* (a b* b b*)* Respondido em 19/11/2022 17:11:35 Explicação: Gabarito: ( b* a b* a b* )* Justificativa: Observe que a única alternativa em que se pode garantir que haverá a ocorrência de zero ou outro número par de 'a' é ( b* a b* a b* )*. Nas demais alternativas, sempre é possível gerar uma palavra com número ímpar de 'a'. Acerto: 0,0 / 1,0 Seja a seguinte gramática S → aSa | bSb | a | b Palíndromos são cadeias do tipo wwr, ou seja, aqueles que lidos da esquerda para a direita ou vice e versa, são iguais. A linguagem gerada pela gramática acima sobre o alfabeto {a, b) é o conjunto de: Todos os palíndromos de comprimento par. Todos os palíndromos. Σ = {a, b} L = {ω|ω ∈ Σ ∗ e o n° de a's em ω é par} Questão5 a Questão6 a Questão7 a Cadeias que começam e terminam com símbolos diferentes. A gramática não gera palíndromos. Todos os palíndromos de comprimento ímpar. Respondido em 19/11/2022 17:23:26 Explicação: Gabarito: Todos os palíndromos de comprimento ímpar. Justificativa: Realizando algumas derivações como exemplo pode-se perceber que a alternativa b é a correta, por exemplo: S → aSa → S → aaa; S → aSa → S → abSba → ababa. Acerto: 0,0 / 1,0 Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC, é denominada de: Infinita. Finita. Sem contexto. Irrestrita (sem restrições). Recursiva. Respondido em 19/11/2022 17:22:52 Explicação: Gabarito: Finita. Justificativa: Uma linguagem L gerada a partir de uma dada GLC é finita se não houver ciclos no grafo direcionado gerado a partir das regras de produção dessa GLC. Acerto: 1,0 / 1,0 Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas. I. A descoberta do cientista implica P = NP. PORQUE II. A descoberta do cientista implica na existê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 verdadeiras e a II é uma justificativa correta da I. A asserção I é uma proposição verdadeira e a II é uma proposição verdadeira. As asserções I e II são proposições falsas. As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I. A asserção I é uma proposição falsa e a II é uma proposição verdadeira. Respondido em 19/11/2022 17:24:16 Explicação: Sabemos que P ⊆ 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 Questão8 a Questão9 a solução ainda pode ser verificada em tempo polinomial. Um problema NP-completo é pelo menos tão difícil quanto qualquer outro problema NP. Para esse caso hipotético, por redução, implica que P=NP e a asserção I é verdadeira. Uma vez que P=NP, existem algoritmos polinomiais para todos os problemas NP e a proposição II é verdadeira e uma justificativa da I. Acerto: 0,0 / 1,0 Seja uma MT T dada pelas quíntuplas: 1. (0, 1, 1, 0, D) 2. (0, b, 1, 1, H)Considere que 0 é um estado inicial e 1 é um estado final e a configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é o tamanho da cadeia, neste caso igual a 3. Qual a função que calcula essa MT? 2n+1 - 1 2n+1 2n -1 2n +1 2n Respondido em 19/11/2022 17:24:38 Explicação: Esse exemplo mostra o poder de computação das MT. Deve-se começar utilizando a quíntupla 1. Enquanto a MT ler 1 na fita, escreve 1, continua no estado 0 e anda para a direita (D). Ao encontrar um branco, escreve 1, muda para o estado final 1 e para (H). A cadeia final é 1111. A cadeia inicial era 111 = 23-1, foi transformada em 1111 = 24-1. Logo a MT calcula 2n+1 - 1 Questão10 a javascript:abre_colabore('38403','300068133','5949517803');