Questões sobre Linguagens Formais e Autômatos

Prévia do material em texto

17/06/2023, 12:06 EPS
https://simulado.estacio.br/alunos/ 1/4
Disciplina: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES  AV
Aluno: LEONARDO DE SENA SOUZA MAGRI 202001546839
Professor: ALTAMIRA DE SOUZA QUEIROZ
ROBSON LORBIESKI
 
Turma: 9001
ARA0309_AV_202001546839 (AG)   22/05/2023 21:40:05 (F) 
Avaliação: 3,00 pts Nota SIA: 3,00 pts
O aproveitamento da Avaliação Parcial será considerado apenas para as provas com nota maior ou igual a 4,0.
 
03491 - CONCEITOS BÁSICOS DE AUTÔMATOS E LINGUAGENS  
 
 1. 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, 5, 6, 7, 8, 10}.
{3, 4, 9, 10, 11}.
{3, 4, 5, 6, 7, 10, 11}.
{0, 1, 2, 8, 10, 11}.
 {5, 6, 7, 8, 10, 11}.
 2. Ref.: 6101939 Pontos: 0,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.
 
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101719.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101939.');
17/06/2023, 12:06 EPS
https://simulado.estacio.br/alunos/ 2/4
Assinale a alternativa que tem uma derivação correta para a expressão id + (id * id):
T =>4 F =>5 (E) =>1(E + T) =>3 (E + T*F) =>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 =>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 =>2 T + T =>4 T + F =>5 T + (E) =>2 T + (T) =>3 T + (T * F) =>4 F + (F * F) =>6 id + (id * id).
 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.
 00c00, 1100011, 00100, c
00c1, 001c100, 00c10, c
0c0, 110c111, 001c100, c
00c10, 11c11, 01c11, c
 0c0, 11c11, 001c100, c
 
03492 - LINGUAGENS REGULARES  
 
 4. Ref.: 6096596 Pontos: 0,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 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.
As palavras com número ímpar de zeros e par 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.
 5. Ref.: 6096710 Pontos: 0,00  / 1,00
(POSCOMP / 2009) Qual é a linguagem da gramática com as seguintes regras de produção:
S → ASb | c
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6101772.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096596.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6096710.');
17/06/2023, 12:06 EPS
https://simulado.estacio.br/alunos/ 3/4
A → a
 
 
 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):
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 a a�rmativa II é falsa.
Somente as a�rmativas II e III são falsas.
 Somente a a�rmativa I é falsa.
 
03493 - LINGUAGENS LIVRES DE CONTEXTO  
 
 7. Ref.: 6097352 Pontos: 1,00  / 1,00
A linguagem gerada pelo GLC é chamada de linguagem livre de contexto (LLC). Acerca de suas características, a
 linguagem livre de contexto não é fechada em relação a:
União.
Fechamento de Kleene.
Concatenação.
 Complementação.
Divisão.
{ancbn|n ∈ N}
{acnb|n ∈ N}
{acbn|n ∈ N}
{ancb|n ∈ N}
{ancnb|n ∈ N}
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097036.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097352.');
17/06/2023, 12:06 EPS
https://simulado.estacio.br/alunos/ 4/4
 8. Ref.: 6097520 Pontos: 0,00  / 1,00
Se ∑ = {1}, então ∑* - ∑+ é
{1}
 {λ, 1, 11¿..}
1*
 λ
1+
 
03494 - COMPUTABILIDADE E A MÁQUINA DE TURING  
 
 9. Ref.: 6113721 Pontos: 0,00  / 1,00
Considere dois problemas de decisão PA e PB, sendo PA indecidível e PB decidível. Observe também dois
problemas de decisão PC e PD, cuja decidibilidade é desconhecida. Suponha que seja possível construir de forma
correta as seguintes reduções:
· de PA para PC.
· de PD para PA.
· de PD para PB.
Com base no cenário descrito, assinale a alternativa correta.
 
 PC é indecidível e PD é decidível.
PC e PD são ambos indecidíveis.
 PC é indecidível, contudo não se pode a�rmar nada sobre a decidibilidade de PD.
Não se pode a�rmar nada sobre a decidibilidade dos problemas PC e PD.
Não se pode a�rmar nada sobre a decidibilidade de PC, porém PD é decidível.
 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.
 
Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G1) ∩ L(G2) = ∅, é
indecidível.
 Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2).
O problema da parada de uma máquina de Turing é indecidível.
Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela
máquina de Turing.
 É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par.
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6097520.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113721.');
javascript:alert('C%C3%B3digo da quest%C3%A3o: 6113811.');