Simulado de Linguagens Formais, Autômatos e Compiladores

Prévia do material em texto

Meus
Simulados
Teste seu conhecimento acumulado
 
Disc.: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES 
Aluno(a): RODRIGO LUIZ SENA FIALHO 202109048635
Acertos: 5,0 de 10,0 14/11/2022
 
 
Acerto: 0,0 / 1,0
Considere as afirmativas abaixo e marque a única alternativa correta:
 
I. um conjunto finito e não vazio Σ de símbolos, é chamado de alfabeto.
II. A partir dos símbolos individuais nós construímos cadeias, que são sequências finitas ou infinitas de
símbolos do alfabeto, concatenados.
III. Uma linguagem formal é um conjunto, finito ou infinito, de cadeias, formadas pela concatenação de
elementos de um alfabeto finito e não-vazio.
Apenas a alternativa II está correta
Apenas as alternativas I e II estão corretas
Apenas as alternativas II e III estão corretas
 Apenas a alternativa III está correta
 As alternativas I, II e III estão corretas
Respondido em 14/11/2022 16:53:36
 
 
Explicação:
Um alfabeto é um conjunto finito e não vazio de símbolos. Os símbolos formam as cadeias por meio da
operação de concatenação. Um conjunto, finito ou infinito, de cadeias, formadas pela concatenação de
elementos de um alfabeto finito e não-vazio é uma linguagem formal. De acordo com o exposto no texto, todas
as alternativas estão corretas.
 
 
Acerto: 0,0 / 1,0
Referência: elaborado pelo autor, adaptado do livro Linz, Peter. An Introduction to Formal Languages and
Automata, 6. Ed. Jones & Bartlett Learning, 2016.
 
(a, b)* significa
 Qualquer combinação de a, b incluindo nulo
Qualquer combinação de a, b, mas 'a' virá primeiro
 Qualquer combinação de a, b excluindo nulo
Qualquer combinação de a, b, mas 'b' virá primeiro
λ
 Questão1
a
 Questão2
a
https://simulado.unifbv.com.br/alunos/inicio.asp
javascript:voltar();
Respondido em 14/11/2022 16:47:06
 
 
Explicação:
Utilizando o fecho de Kleene, sabemos que a expressão (a, b)* gera qualquer combinação de cadeias compostas
pelos símbolos a e b e, necessariamente, inclui a cadeia nula λ. Neste caso, a ordem em que aparecem os
símbolos nas cadeias não requer que "a" venha antes de "b". Se isso fosse necessário escreveríamos (ab)*
 
 
Acerto: 0,0 / 1,0
Referência: elaborado pelo autor, adaptado do livro Linz, Peter. An Introduction to Formal Languages and
Automata, 6. Ed. Jones & Bartlett Learning, 2016.
 
Assinale a alternativa correta
a = a + a
a* = a+. a+
 a+ = a*. a
 a* = a+. a*
a+ = a*. a*
Respondido em 14/11/2022 17:27:48
 
 
Explicação:
De acordo com o fecho de Kleene, a* são todas as cadeias formadas por um número indeterminado de "a",
incluindo a cadeia nula λ. Todas as cadeias formadas por um número indeterminado de "a", não incluindo a
cadeia nula λ, é representado por a+. a+ é, exatamente, "a*.a", evitando que a cadeia nula venha a aparecer
nessa linguagem.
 
 
Acerto: 1,0 / 1,0
Vamos considerar que em uma classe 32 alunos gostam de Geografia e 40 de História. Sabendo que a classe
possui 60 alunos, qual o número de alunos que gostam de Geografia e de História?
20
 No mínimo 12
32
No máximo 12
36
Respondido em 14/11/2022 16:57:49
 
 
Explicação:
Gabarito: No mínimo 12
Justificativa: O conjunto universo tem 60 alunos. O conjunto dos que gostam de geografia tem 32 e o
conjunto dos que gostam de história tem 40. Logo, a intersecção de ambos tem, pelo menos, 12 alunos que
gostam de ambas as disciplinas.
 
 
Acerto: 0,0 / 1,0
Considerando a teoria dos conjuntos, qual das alternativas abaixo está correta?
 Questão3
a
 Questão4
a
 Questão5
a
S ∩ ∅ = S
 S U ∅ = S - ∅ = S
S U ∅ = S - ∅ = ∅
 S U ∅ = ∅
S - ∅ = ∅
Respondido em 14/11/2022 17:18:35
 
 
Explicação:
Gabarito: S U ∅ = S - ∅ = S
Justificativa: A união de qualquer conjunto com o conjunto vazio é igual ao próprio conjunto, bem como a
diferença de um conjunto com o conjunto vazio é o próprio conjunto. Assim, a única alternativa correta é S U ∅
= S - ∅ = S.
 
 
Acerto: 1,0 / 1,0
(POSCOMP / 2008 - adaptada) Analise as seguintes igualdades de expressõ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 é verdadeira.
somente a igualdade I é verdadeira.
 somente as igualdades I e II são verdadeiras.
somente as igualdades II e III são verdadeiras.
somente a igualdade II é verdadeira.
Respondido em 14/11/2022 17:20:55
 
 
Explicação:
Gabarito: somente as igualdades I e II são verdadeiras.
Justificativa: a* + b* significa 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 é
verdadeira porque segundo o fecho de Kleene podemos considerar Σ = {a, b} e Σ* definido como o conjunto de
todas as cadeias, incluindo a cadeia nula, portanto as linguagens são iguais e geradas por expressões
equivalentes. A alternativa I é, claramente, verdadeira, bastando retirar os parênteses da expressão à direita.
 
 
Acerto: 1,0 / 1,0
Com base nas afirmativas abaixo assinale a resposta correta:
I. Alfabeto ou vocabulário "V" é um conjunto finito e não vazio de símbolos.
II. Uma palavra sobre o alfabeto "V" é uma cadeia de comprimento finito de símbolos de "V".
III. Gramáticas são especificações infinitas de linguagens finitas.
IV. A classe das linguagens regulares é um subconjunto próprio da classe das linguagens livres de contexto.
 I, II e IV, apenas.
I e IV, apenas.
I, II e III, apenas.
 Questão6
a
 Questão7
a
II e III, apenas.
II e IV, apenas.
Respondido em 14/11/2022 17:22:40
 
 
Explicação:
Gabarito: I, II e IV, apenas.
Justificativa: Gramáticas são especificações finitas de linguagens infinitas. A afirmativa III está errada.
 
 
Acerto: 1,0 / 1,0
Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias. Nesse sentido,
assinale a alternativa incorreta.
λ ∈ Σ*
V ∩ T = ∅
 V ∩ T = Σ*
V U T = Σ
a + b denota {a} U {b} = {a, b}
Respondido em 14/11/2022 17:24:05
 
 
Explicação:
Gabarito: V ∩ T = Σ*
Justificativa: 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. Todas as demais alternativas estão corretas.
 
 
Acerto: 0,0 / 1,0
Para resolver problemas, precisamos construir algoritmos. Para esses algoritmos, suas complexidades
precisam ser calculadas, as quais são necessárias para analisar os algoritmos e encontrar o mais adequado. 
Considere as seguintes quatro funções:
f1 (n) = 2n
f2 (n) = n2
f3 (n) = 2n2
f4 (n) = 2n + 3
 
Quais das seguintes sentenças matemáticas são verdadeiras?
I. para n > 0, f2 (n) < f3 (n)
II. para n > 2, f1 (n) < f2 (n)
III. para n = 0, f2 (n) < f3 (n)
IV. para n < 2, f1 (n) < f2 (n)
V. para n > 2, f3 (n) < f4 (n)
 
somente I, III e IV.
 somente I, II e V.
somente III, IV e V.
 Questão8
a
 Questão9
a
 somente I e II.
somente II, III e IV.
Respondido em 14/11/2022 17:25:19
 
 
Explicação:
Consideremos a seguinte tabela:
Função n = 0 n = 2 n = 10 n = 20
f1(n) 0 4 20 40
f2(n) 0 4 100 400
f3(n) 0 8 200 800
f4(n) 4 7 1027 1.048.579
 
É fácil observar que para n = 0, f2 (n) = f3 (n) = 0 e que para n < 2, f1 (n) = f2 (n) = 0, logo são falsas; as
sentenças I, II e V são verdadeiras.
 
 
Acerto: 1,0 / 1,0
O problema da parada para máquinas de Turing, ou simplesmente problema da parada, pode ser assim
descrito: determinar, para qualquer máquina de Turing M e palavra w, se M irá eventualmente parar com
entrada w. Mais informalmente, o mesmo problema também pode ser assim descrito: dados um algoritmo e
uma entrada finita, decidir se o algoritmo termina ou se executará indefinidamente. Para o problema da
parada:
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução polinomial
que o soluciona, fornecendo respostas aproximadas.
Existe algoritmoexato de tempo de execução polinomial para solucioná-lo.
Existe algoritmo exato de tempo de execução exponencial para solucioná-lo.
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de execução exponencial
que o soluciona, fornecendo respostas aproximadas. 
 Não existe algoritmo que o solucione, não importa quanto tempo seja disponibilizado. 
Respondido em 14/11/2022 17:26:17
 
 
Explicação:
Não existe nenhuma máquina de Turing M que consiga decidir se vai parar ou entrar em loop infinito. O
problema da parada é indecidível, portanto não existe algoritmo que o solucione.
 
 
 
 
 
 
 
 
 
 
 
 Questão10
a
javascript:abre_colabore('38403','299474822','5934715426');