Simulado 1 Linguagens formais e autômatos

Prévia do material em texto

08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/9
Acerto: 1,0 / 1,0
Considere as seguintes regras de gramática, onde "|" representa "ou", λ representa a cadeia vazia e undrscr é o caractere "_".
 
1. →
2. → 
3. →
4. → 
5. → 
6. → λ
7. → a | b | ... | z | A | B | ... | Z
8. → 0 | 1 | ... | 9
9. → _
 
Assinale a cadeia que pode ser gerada pela aplicação das produções na seguinte ordem:1, 7, 3, 7, 5, 9, 4, 8, 6
ab_
a0
 ab_9
_ab9
7b1
Respondido em 08/11/2022 20:24:20
Explicação:
Sabemos que as cadeias são geradas a partir do emprego das regras de produção. Aplicando a regra 1 temos ⇒. Na sequência
aplica-se a regra 7 onde foi substituída por uma letra, portanto, fica estabelecido que essa cadeia irá iniciar por uma letra, o que
já elimina as alternativas "d" e "e". Neste ponto estamos em a, supondo que a letra que foi substituída é "a" já que todas as
alternativas iniciam com a letra "a". Em seguida, é aplicada a regra 3 e ficamos com a cadeia a< resto >.
Aplicando a regra 7 substituímos a por "b", o que elimina a alternativa "b". Neste ponto estamos com a cadeia ab. Aplicando a
regra 5 ficamos com ab . Pela regra 9 geramos ab_. Pela regra 4 ab_. A regra 8 aplicada gera ab_9, ou qualquer outro dígito,
mas para o caso em questão nos interessa o 9.
Ao aplicar a regra 6 substituímos pela cadeia nula (λ) e geramos ab_9.
As produções podem ser desenvolvidas como segue:
 Questão2
a
08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/9
⇒⇒a⇒a ⇒ ab ⇒ ab
⇒ab_⇒ab_ ⇒ab_9.
Acerto: 1,0 / 1,0
Considere, a seguir, a gramática livre de contexto G = (V, T, P, S), onde V = {S}, T = {a,b,c}, e P:
S → aS|Sb|c
 
Qual expressão regular gera a mesma linguagem que a gramática definida acima?
anc bn, onde n ≥ 0
 an c bm, onde n, m ≥ 0
ca+ b+
a+ b+ c
an c bm, onde n, m ≥ 1
Respondido em 08/11/2022 21:34:31
Explicação:
Aplicando algumas regras de produção podemos inferir a lei geral de formação de cadeias dessa linguagem. S → c. Isso equivale
a λcλ. Logo n, m ≥ 0, eliminamos as alternativas de a) até c), uma vez que pode haver cadeias sem símbolos ¿a¿ e/ou ¿b¿.
Sejam os exemplos: S → aS⇒ac e S → Sb⇒cb. Esses dois exemplos 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: 1,0 / 1,0
Com base nas afirmativas abaixo assinale a resposta correta:
I. As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos finitos.
II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0.
III. Em todo autômato finito existe sempre um estado inicial fixo.
IV. Gramáticas têm um número finito de regras de produção.
I e IV, apenas.
 Questão3
a
 Questão4
a
08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/9
 I, III e IV, apenas
II e III, apenas
II e IV, apenas
I, II e IV, apenas
Respondido em 08/11/2022 17:18:36
Explicação:
Gabarito: I, III e IV, apenas
Justificativa: As linguagens regulares são as do tipo 3 e não do tipo 0. As demais alternativas estão corretas.
Acerto: 1,0 / 1,0
(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
Gramática livre de contexto.
 Gramática regular.
Gramática de pilha.
Gramática irrestrita.
Gramática sensível ao contexto.
Respondido em 08/11/2022 16:49:36
Explicação:
Gabarito: Gramática regular.
Justificativa: A primeira fase do compilador chamada analisador léxico é projetada pelos autômatos finitos, que são os
reconhecedores das expressões regulares geradas pelas gramáticas regulares.
Acerto: 1,0 / 1,0
(POSCOMP / 2008) Considere o autômato finito mostrado na figura abaixo (os círculos em negrito representam estados
terminais)
 Questão5
a
 Questão6
a
08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 5/9
A esse respeito, assinale a afirmativa FALSA.
A palavra vazia é reconhecida pelo autômato.
A palavra aaa é reconhecida pelo autômato.
A palavra baba é reconhecida pelo autômato.
A palavra ababa não é reconhecida pelo autômato.
 A palavra aba é reconhecida pelo autômato.
Respondido em 08/11/2022 15:00:54
Explicação:
Gabarito: A palavra aba é reconhecida pelo autômato.
Justificativa: Esse AFN realiza uma transição em ε para um estado final, logo reconhece a palavra 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 verdadeiras. A palavra aba não é reconhecida pelo autômato porque não há caminhos que levem a um
estado final. Essa alternativa é falsa.
Acerto: 1,0 / 1,0
Considere as seguintes produções da gramática da linguagem C e assinale a opção que não está em BNF:
< inclusive-or-expression > ::= < exclusive-or-expression >
 | < inclusive-or-expression > | < exclusive-or-expression >
< conditional-expression > ::= < logical-or-expression >
 | < logical-or-expression > ? < expression > : < conditional-expression >
 < logical-or-expression > →
 | < logical-or-expression > || < logical-and-expression >
< and-expression > ::= < equality-expression >
 | < and-expression > & < equality-expression >
< logical-and-expression > ::= < inclusive-or-expression >
 Questão7
a
08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 6/9
 | < logical-and-expression > && < inclusive-or-expression >
Respondido em 08/11/2022 17:33:49
Explicação:
Gabarito:
< logical-or-expression > → < logical-and-expression >
 | < logical-or-expression > || < logical-and-expression >
Justificativa: Não se usa → na BNF. A forma correta quando se utiliza BNF é a utilização do símbolo ::=
Acerto: 0,0 / 1,0
Considere a seguinte propriedade sobre uma linguagem formal L: ¿Existe um número natural n ≥ 0, tal que para qualquer
palavra w ∈ L:
1. Todo z ∈ L com z ≥ n pode ser escrito como w = uvwxy, para algumas cadeias u,v,w,x,y.
2. |vx| ≥ 1
3. |vwx| ≤ n
4. uvkwxky ∈ L para todo k ≥ 0
 
Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F (falso) para as afirmativas a seguir.
( ) Se L é aceita por PDA, então L satisfaz a propriedade acima.
( ) L = {0p; onde p é primo} não satisfaz a propriedade acima.
( ) A propriedade acima é falsa para a linguagem L = {WcWR | W ∈ (a, b)*}
( ) A linguagem {anbncn; n ≥ 0} não satisfaz a propriedade acima.
( ) O lema do bombeamento para linguagem livre de contexto é usado para provar que certos conjuntos são livres de
contexto.
Assinale a alternativa que contém, de cima para baixo, a sequência correta:
 V, F, V, F, F.
 V, V, F, V, F.
F, V, V, F, V.
V, V, V, V, F.
F, V, F, V, V.
Respondido em 08/11/2022 20:19:12
 Questão8
a
08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 7/9
Explicação:
Gabarito: V, V, F, V, F.
Justificativa:
1. Esse é o lema do bombeamento para LLC e toda LLC é reconhecida por um PDA.
2. Aplicando o lema é possível provar que 0p não é livre de contexto e não satisfaz a propriedade.
3. WcWR é LLC, logo a propriedade é verdadeira e a afirmativa é falsa.
4. Está correta conforme pode ser lido no Módulo 4, núcleo conceitual 1.
5. O lema do bombeamento para linguagem livre de contexto é usado para provar que certos conjuntos não são livres de
contexto. Alternativa falsa.
Acerto: 1,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 II, III e IV.
somente I e II.
 Questão9
a
08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 8/9
somente I, III e IV.
somente III, IV e V.
 somente I, II e V.
Respondido em 08/11/2022 16:09:22
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
Uma redução é um processo de conversão de um problema em outro problema resolvido de tal forma que a solução do
segundo problema possa ser usada para resolver o primeiro problema. Em particular, a redutibilidade pode ser usada para
demonstrar que problemas são indecidíveis ou decidíveis. Nesse contexto, avalie as seguintes afirmativas:
I. A Redutibilidade não diz nada em resolver os problemas A ou B sozinhos, mas somente sobre a resolução de A na
presença de um método para resolver B.
II. Reduções apresentam um importante papel em classificar os problemas em decidíveis ou indecidíveis.
III. Se A é redutível a B e B é um problema indecidível, então A é um problema decidível.
 
Quais as afirmativas verdadeiras?
I, II e III.
II e III.
III.
I e III.
 I e II.
Respondido em 08/11/2022 15:54:07
 Questão10
a
08/11/2022 21:38 Estácio: Alunos
https://simulado.estacio.br/alunos/ 9/9
Explicação:
Na afirmativa III, se A é redutível a B e B é um problema indecidível, então A é um problema indecidível.
javascript:abre_colabore('38403','298389716','5904094896');