Prova LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES

Prévia do material em texto

09/06/2024, 09:54 EPS
https://simulado.estacio.br/alunos/ 1/4
Disciplina: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES  NC
Aluno: RAFAEL PATRICIO DA CUNHA 202001624961
Turma: 9001
ARA0309_NC_202001624961 (AG)   25/11/2023 09:00:41 (F) 
Avaliação: 7,00 pts de 10,00 Nota SIA: 7,00 pts
 
03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS  
 
 1. Ref.: 6101939 Pontos: 1,00  / 1,00
Seja G = (V, T, P, E), onde V = {+, *, (, ), id, T, F, E}, T = {+, *, (, ), id} e P:
 
1. E → E + T                        4. T → F
2. E → T                              5. F → (E)
3. T → T * F                         6. F → id
 
Os símbolos E, T,  F são abreviaturas para expressão, termo e fator, respectivamente e id é um identi�cador válido
dessa linguagem.
 
Assinale a alternativa que tem uma derivação correta para a expressão id + (id * id):
 E =>1 E + T =>2 T + T =>4 T + F =>5 T + (E) =>2 T + (T) =>3 T + (T * F) =>4 F + (F * F) =>6 id + (id * id).
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id / (id - id).
E =>1 E + T =>3 E + T * F =>5 E + T * (E) =>1 E + T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id).
T =>3 T * F =>5 T * (E) =>1 T * (E + T) =>2 T * (T + T) =>4 F * (F + F) =>6 id * (id + id).
T =>4 F =>5 (E) =>1(E + T) =>3 (E + T*F) =>4 (F + F*F) =>6 (id + id *id).
 2. Ref.: 6101664 Pontos: 0,00  / 1,00
BIO-RIO - 2014 - ETAM - Curso de Formação de Técnicos - 1º Semestre
Considere os conjuntos A = {1, 2, 3, 4, 5} e B = {4, 5, 6, 7, 8, 9} e a função f: A → B dada por f(x) = x + 4. O conjunto
imagem dessa função é:
 {5, 6, 7, 8}
 {5, 6, 7, 8, 9}
{4, 5, 6, 7, 8}
{4, 5, 6, 7, 8, 9}
{4, 5, 6, 7}
 3. Ref.: 6101909 Pontos: 1,00  / 1,00
Palíndromos são cadeias que lidas da esquerda para a direita ou da direita para a esquerda têm a mesma sequência
de símbolos e podem ser de�nidas pela seguinte expressão: wwR, onde w é uma cadeia e não há constante ou
separador. Nesse contexto, assinale a alternativa em que todas as cadeias são palíndromos sem separador.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101664.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101664.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101909.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101909.');
09/06/2024, 09:54 EPS
https://simulado.estacio.br/alunos/ 2/4
001, 1190911, 0010, AABB
010, 1190911, 00100, ANA
001, 1199911, 0010, AABB
 00, 119911, 001100, AA
ANA, 1190911, 0010, ABA
 
03492 - LINGUAGENS REGULARES  
 
 4. Ref.: 6097098 Pontos: 0,00  / 1,00
A teoria dos autômatos é o estudo de máquinas _______________ e os problemas computacionais relacionados a essas
máquinas, chamadas de _______________. São aplicados em diferentes áreas da ciência da computação e da
_______________. Sua aplicação mais tradicional é encontrada na construção de _______________.
Assinale a alternativa que preenche, correta e respectivamente, as lacunas do trecho acima.
determinísticas - computadores - matemática - circuitos elétricos
 abstratas - autômatos - engenharia - compiladores
automáticas - compiladores - engenharia - corretores ortográ�cos
de estado �nito - computadores - TI - computadores
 abstratas - compiladores - engenharia - computadores
 5. Ref.: 6096596 Pontos: 1,00  / 1,00
Considere o seguinte Autômato Finito
Sobre o autômato apresentado, assinale a a�rmativa correta.
As palavras com número ímpar de zeros e par de uns são reconhecidas pelo autômato.
As palavras com número ímpar de zeros e uns são reconhecidas pelo autômato.
 As palavras com número par de zeros e ímpar de uns são reconhecidas pelo autômato.
A palavra vazia é reconhecida pelo autômato.
As palavras com número par de zeros e uns são reconhecidas pelo autômato.
 6. Ref.: 6097036 Pontos: 1,00  / 1,00
(POSCOMP / 2008) Seja o autômato �nito mostrado na �gura abaixo que opera sobre o alfabeto Σ = {a,b} (o círculo
em negrito indica um estado terminal):
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.');
09/06/2024, 09:54 EPS
https://simulado.estacio.br/alunos/ 3/4
Analise as seguintes a�rmativas.
I. O autômato �nito mostrado na �gura é determinístico.
II. O autômato �nito mostrado na �gura é não-determinístico.
III. O autômato �nito mostrado na �gura reconhece a palavra vazia
A análise permite concluir que
Somente as a�rmativas I e II são falsas.
 Somente a a�rmativa I é falsa.
Somente a a�rmativa II é falsa.
Somente as a�rmativas II e III são falsas.
Somente a a�rmativa III é falsa.
 
03493 - LINGUAGENS LIVRES DE CONTEXTO  
 
 7. Ref.: 6097520 Pontos: 1,00  / 1,00
Se ∑ = {1}, então ∑* - ∑+ é
1*
1+
{λ, 1, 11¿..}
 λ
{1}
 8. Ref.: 6097350 Pontos: 1,00  / 1,00
(ENADE / 2011) Considere a gramática a seguir em que S, A e B são símbolos não terminais, 0 e 1 são terminais e ε é a
cadeia vazia.
                S → 1S | 0A | ε
                A → 1S | 0B | ε
                B → 1S | ε
A respeito dessa gramática, analise as a�rmações a seguir.
I. Nas cadeias geradas por essa gramática, o último símbolo é sempre 1.
II. O número de zeros consecutivos nas cadeias geradas pela gramática é, no máximo, dois.
III. O número de uns em cada cadeia gerada pela gramática é maior que o número de zeros.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097520.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097520.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097350.');
09/06/2024, 09:54 EPS
https://simulado.estacio.br/alunos/ 4/4
IV. Nas cadeias geradas por essa gramática, todos os uns estão à esquerda de todos os zeros.
É correto apenas o que se a�rma em:
II e IV
I
I e III
III e IV
 II
 
03494 - COMPUTABILIDADE E A MÁQUINA DE TURING  
 
 9. Ref.: 6113714 Pontos: 1,00  / 1,00
Embora uma máquina de Turing seja uma estrutura muito simples, ela é extremamente poderosa. Acerca de suas
características, uma linguagem L é chamada aceitável, se existe uma máquina de Turing M que:
 
I) Entra em loop in�nito para cadeias em L.
II) Aceita L.
III) Rejeita L.
IV) Resolve o problema em um tempo de execução polinomial.
V) Resolve o problema da Parada.
IV e V.
II e III.
 I, II e III.
I, III e V.
III, IV e V.
 10. Ref.: 6113811 Pontos: 0,00  / 1,00
  Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens da hierarquia de
Chomsky e suas respectivas máquinas reconhecedoras, analise as a�rmações a seguir e assinale a falsa.
 
O problema da parada de uma máquina de Turing é indecidível.
 Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G1) ∩ L(G2) = ∅, é
indecidível.
Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela
máquina de Turing.
Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2).
 É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.');