LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES av

Prévia do material em texto

24/06/2023, 18:34 EPS
https://simulado.estacio.br/alunos/ 1/5
Disciplina: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES  AV
Aluno: VICTOR MIGUEL DA SILVA 201703488989
Professor: ALTAMIRA DE SOUZA QUEIROZ
ROBSON LORBIESKI
 
Turma: 9001
ARA0309_AV_201703488989 (AG)   26/05/2023 17:15:20 (F) 
Avaliação: 8,00 pts Nota SIA: 10,00 pts
 
03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS  
 
 1. Ref.: 6101664 Pontos: 1,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, 9}
{4, 5, 6, 7, 8, 9}
{4, 5, 6, 7}
{5, 6, 7, 8}
{4, 5, 6, 7, 8}
 2. Ref.: 6101719 Pontos: 1,00  / 1,00
CONSULPLAN - 2016 - CBM-PA - Aspirante do Corpo de Bombeiro
Observe os conjuntos a seguir.
 
O conjunto formado pela operação (A - C) ∪ (B ∩ C) é:
 
{0, 1, 2, 8, 10, 11}.
{3, 4, 9, 10, 11}.
{3, 4, 5, 6, 7, 10, 11}.
 {5, 6, 7, 8, 10, 11}.
{0, 1, 2, 5, 6, 7, 8, 10}.
 3. Ref.: 6101772 Pontos: 0,00  / 1,00
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101664.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101719.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.');
24/06/2023, 18:34 EPS
https://simulado.estacio.br/alunos/ 2/5
Considere a seguinte gramática: G = {S, (0, 1, c), (S→0S0, S→1S1, S→c), S}. Assinale a alternativa que contém,
apenas, cadeias geradas por essa gramática.
 0c0, 11c11, 001c100, c
00c1, 001c100, 00c10, c
 00c00, 1100011, 00100, c
00c10, 11c11, 01c11, c
0c0, 110c111, 001c100, c
 
03492 - LINGUAGENS REGULARES  
 
 4. Ref.: 6096597 Pontos: 1,00  / 1,00
Considere o autômato �nito mostrado na �gura abaixo (os círculos concêntricos representam estado �nal) e assinale
a a�rmativa correta.
 A palavra vazia é reconhecida pelo autômato.
A palavra 01010 não é reconhecida pelo autômato.
A palavra vazia não é reconhecida  pelo autômato.
A palavra 101 é reconhecida pelo autômato.
A palavra 10101 é reconhecida pelo autômato.
 5. Ref.: 6097098 Pontos: 1,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
de estado �nito - computadores - TI - computadores
abstratas - compiladores - engenharia - computadores
automáticas - compiladores - engenharia - corretores ortográ�cos
 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: 6096597.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097098.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.');
24/06/2023, 18:34 EPS
https://simulado.estacio.br/alunos/ 3/5
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 II é falsa.
Somente a a�rmativa III é falsa.
Somente as a�rmativas II e III são falsas.
 Somente a a�rmativa I é falsa.
 
03493 - LINGUAGENS LIVRES DE CONTEXTO  
 
 7. Ref.: 6097520 Pontos: 1,00  / 1,00
Se ∑ = {1}, então ∑* - ∑+ é
{λ, 1, 11¿..}
 λ
1+
1*
{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: 6097350.');
24/06/2023, 18:34 EPS
https://simulado.estacio.br/alunos/ 4/5
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:
III e IV
 II
I e III
II e IV
I
 
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.
I, III e V.
II e III.
IV e V.
III, IV e V.
 I, II e III.
 10. Ref.: 6113910 Pontos: 0,00  / 1,00
Considere os seguintes problemas de decisão:
 
P1: Uma determinada máquina de estado �nito aceita uma determinada cadeia.
P2: Uma determinada gramática livre de contexto gera um número in�nito de cadeias.
Qual das seguintes a�rmações é verdadeira?
Apenas P1 é decidível.
 Nem P1 nem P2 são decidíveis.
Apenas P2 é decidível.
 Ambos P1 e P2 são decidíveis.
P1 e P2 não são problemas de decisão.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113910.');
24/06/2023, 18:34 EPS
https://simulado.estacio.br/alunos/ 5/5