AVS - Linguagens formais, autômatos e compiladores

Prévia do material em texto

Disciplina: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES  AV
Aluno: IARA CATARINA SILVA E LIMA 202110051628
Professor: ALTAMIRA DE SOUZA QUEIROZ
ROBSON LORBIESKI
 
Turma: 9001
ARA0309_AV_202110051628 (AG)   10/04/2023 18:55:58 (F) 
Avaliação: 6,00 pts Nota SIA: 8,00 pts
 
03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS  
 
 1. 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.
001, 1199911, 0010, AABB
010, 1190911, 00100, ANA
 00, 119911, 001100, AA
001, 1190911, 0010, AABB
ANA, 1190911, 0010, ABA
 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 é:
{4, 5, 6, 7}
 {5, 6, 7, 8}
 {5, 6, 7, 8, 9}
{4, 5, 6, 7, 8, 9}
{4, 5, 6, 7, 8}
 3. Ref.: 6101772 Pontos: 0,00  / 1,00
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.
00c10, 11c11, 01c11, c
0c0, 110c111, 001c100, c
 0c0, 11c11, 001c100, c
00c1, 001c100, 00c10, c
 00c00, 1100011, 00100, c
 
03492 - LINGUAGENS REGULARES  
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101909.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101664.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.');
 4. 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 par de zeros e uns são reconhecidas pelo autômato.
As palavras com número ímpar de zeros e uns são reconhecidas pelo autômato.
A palavra vazia é reconhecida pelo autômato.
 As palavras com número par de zeros e ímpar de uns são reconhecidas pelo autômato.
 5. 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 10101 é reconhecida pelo autômato.
 A palavra vazia é reconhecida pelo autômato.
A palavra 101 é reconhecida pelo autômato.
A palavra 01010 não é reconhecida pelo autômato.
A palavra vazia não é reconhecida  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: 6096596.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096597.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.');
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 a a�rmativa III é falsa.
Somente as a�rmativas I e II são falsas.
Somente as a�rmativas II e III são falsas.
Somente a a�rmativa II é falsa.
 Somente a a�rmativa I é falsa.
 
03493 - LINGUAGENS LIVRES DE CONTEXTO  
 
 7. Ref.: 6097522 Pontos: 0,00  / 1,00
(POSCOMP / 2008) Considere a seguinte gramática G, onde S é o símbolo inicial:
               S → AcB
               A → cA | aB
               B → cB | aA
               A → λ
Assinale a alternativa que apresenta a palavra que NÃO pertence à linguagem gerada pela gramática G.
aaca
aaaca
 ccac
 aa
ccca
 8. Ref.: 6097520 Pontos: 0,00  / 1,00
Se ∑ = {1}, então ∑* - ∑+ é
 λ
{1}
1+
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097522.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097520.');
 {λ, 1, 11¿..}
1*
 
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.: 6113920 Pontos: 1,00  / 1,00
Alan Mathison Turing foi um cientista da computação nascido no Reino Unido que dedicou seu trabalho a
desenvolver máquinas de computar. Consoante a teoria da computabilidade, o problema que resulta em sim ou não é
classi�cado como um:
 Problema de decisão.
Problema de redução.
Problema de pesquisa.
Problema de otimização.
Problema funcional.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113714.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113920.');