Atividade Linguagens Formais e Autômatos

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');