LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES 2

Prévia do material em texto

23/10/2022 00:18 Estácio: Alunos
https://simulado.estacio.br/alunos/ 1/4
 
Meus
Simulados
 Teste seu conhecimento acumulado
Quest.: 1
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. Ed. Jones & Bartlett
Learning, 2016.
 
Qual a linguagem gerada pela gramática: G = {(S, A), (0, 1), (S→0S1, S→A, A→0A), S}.
Quest.: 2
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
Lupa Calc.
 
 
Aluno: ALEX SANTOS VIEIRA Matr.: 201903533341
Disciplina: ARA0309 - LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES Período: 2022.2 (G) / SM
 
1.
1m0n
1m0m
λ
0m1n
0m1m
 
2.
ab_
a0
_ab9
javascript:voltar();
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909688679.')
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909688534.')
javascript:diminui();
javascript:aumenta();
javascript:calculadora_on();
23/10/2022 00:18 Estácio: Alunos
https://simulado.estacio.br/alunos/ 2/4
Quest.: 3
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?
Quest.: 4
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.
Quest.: 5
(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
Quest.: 6
(POSCOMP / 2008) Considere o autômato finito mostrado na figura abaixo (os círculos em negrito representam
estados terminais)
A esse respeito, assinale a afirmativa FALSA.
ab_9
7b1
 
3.
an c bm, onde n, m ≥ 1
anc bn, onde n ≥ 0
ca+ b+
a+ b+ c
an c bm, onde n, m ≥ 0
 
4.
I e IV, apenas.
II e III, apenas
I, II e IV, apenas
II e IV, apenas
I, III e IV, apenas
 
5.
Gramática irrestrita.
Gramática de pilha.
Gramática regular.
Gramática livre de contexto.
Gramática sensível ao contexto.
 
6.
A palavra baba é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909688547.')
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909683627.')
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909683775.')
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909683710.')
23/10/2022 00:18 Estácio: Alunos
https://simulado.estacio.br/alunos/ 3/4
Quest.: 7
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:
Quest.: 8
Considere as seguintes produções da gramática da linguagem C e assinale a opção que não está em BNF:
Quest.: 9
Analise as seguintes afirmativas
 
I. Em um problema de decisão, o objetivo é decidir a resposta sim ou não a uma questão. Em um
problema de localização, procura-se localizar uma certa estrutura que satisfaça um conjunto de
propriedades dadas. Se as propriedades envolverem critérios de otimização, então o problema é dito de
otimização.
II. A teoria da complexidade restringe-se a problemas de decisão, já que o estudo de problemas NP-
completos é aplicado somente para esse tipo de problema.
A palavra aaa é reconhecida pelo autômato.
A palavra ababa não é reconhecida pelo autômato.
A palavra aba é reconhecida pelo autômato.
 
7.
V, V, F, V, F.
V, F, V, F, F.
V, V, V, V, F.
F, V, V, F, V.
F, V, F, V, V.
 
8.
< and-expression > ::= < equality-expression >
 | < and-expression > & < equality-expression >
< inclusive-or-expression > ::= < exclusive-or-expression >
 | < inclusive-or-expression > | < exclusive-or-expression >
< logical-and-expression > ::= < inclusive-or-expression >
 | < logical-and-expression > && < inclusive-or-expression >
< conditional-expression > ::= < logical-or-expression >
 | < logical-or-expression > ? < expression > : < conditional-expression >
< logical-or-expression > →
 | < logical-or-expression > || < logical-and-expression >
 
9.
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909684026.')
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909684201.')
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909700418.')
23/10/2022 00:18 Estácio: Alunos
https://simulado.estacio.br/alunos/ 4/4
III. Os problemas NP-Completos são considerados como os problemas mais difíceis em NP. Se qualquer
problema NP-Completo pode ser resolvido em tempo polinomial, então todos os problemas em NP
podem ser resolvidos da mesma forma.
 
A análise permite concluir que:
Quest.: 10
Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo é quadrático,
quanto tempo em segundos ele gastará, aproximadamente, no mesmo computador, se a entrada tiver tamanho
100?
As afirmativas I, II e III estão corretas.
Apenas as afirmativas I e III estão corretas.
Apenas a afirmativa I está correta.
Apenas a afirmativa II está correta.
Apenas as afirmativas I e II estão corretas.
 
10.
10.
500.
100.
20.
40.
 
 
 
 
 Não Respondida Não Gravada Gravada
 
 
 
 
 
javascript:alert('Quest%C3%A3o com o c%C3%B3digo de refer%C3%AAncia 201909700494.')