Simulado Estácio Linguagens Formais Autômatos e Compiladores 2

Prévia do material em texto

1a 
 Questão 
Acerto: 1,0 / 1,0 
 
A análise sintática é usualmente implementada a partir de uma gramática: 
 
 Livre de contexto 
 
Irrestrita 
 
Sensível ao contexto 
 
Com estrutura de frase 
 
Regular 
Respondido em 20/10/2022 09:54:24 
 
Explicação: 
As gramáticas regulares são utilizadas para a análise léxica em compiladores de linguagens 
de programação. A parte gramatical da linguagem é verificada por meio de árvores de 
derivação geradas a partir de gramáticas livres de contexto. 
 
 
2a 
 Questão 
Acerto: 1,0 / 1,0 
 
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. 
Ed. Jones & Bartlett Learning, 2016. 
 
(a, b)+ significa 
 
 Qualquer combinação de a, b excluindo nulo 
 
Qualquer combinação de a, b, mas 'a' virá primeiro 
 
λ 
 
Qualquer combinação de a, b incluindo nulo 
 
Qualquer combinação de a, b, mas 'b' virá primeiro 
Respondido em 20/10/2022 09:55:25 
 
Explicação: 
Utilizando o fecho de Kleene, sabemos que a expressão (a, b)+ gera qualquer combinação 
de cadeias compostas pelos símbolos a e b e, necessariamente, não inclui a cadeia nula λ. 
Neste caso, a ordem em que aparecem os símbolos nas cadeias não requer que "a" venha 
antes de "b". Se isso fosse necessário escreveríamos (ab)+ 
 
 
3a 
 Questão 
Acerto: 0,0 / 1,0 
 
Sejam os conjuntos A com 2 elementos, B com 4 elementos, C com 5 elementos, 
então: 
 
 (A ∪ B) ∪ C tem no máximo 2 elementos 
 (A ∩ B) ∩ C tem no máximo 2 elementos 
 
A ∩ ∅ tem 3 elementos pelo menos 
 A ∪ C tem no máximo 5 elementos 
 
A ∩ B tem no máximo 1 elemento 
Respondido em 20/10/2022 09:55:51 
 
Explicação: 
A intersecção de A com B tem no máximo dois elementos, uma vez que o conjunto A só 
tem dois elementos. Essa intersecção pode ter zero, um ou dois elementos. Isto pode ser 
visto desenhando um diagrama de Venn. A U B terá seis elementos e A U C terá sete 
elementos. Como C tem 5 elementos, mas a intersecção de A com B tem, no máximo dois 
elementos, então (A ∩ B) ∩ C tem, no máximo 2 elementos. 
 
 
4a 
 Questão 
Acerto: 0,0 / 1,0 
 
(POSCOMP / 2016) O autômato finito exposto abaixo representa qual expressão 
regular? 
 
 
 a*b(c + da*b)* 
 a*b (d* + cb) 
 
a*c* (b +d)* 
 
ab*(da* + cb)* 
 
(bb + d)* (aa + c)* 
Respondido em 20/10/2022 09:56:33 
 
Explicação: 
Gabarito: a*b(c + da*b)* 
Justificativa: Esse AF reconhece a*b, uma vez que essa cadeia leva a um estado final. Na 
sequência deve reconhecer qualquer número de entradas de 'c' e deixar o estado quando 
receber uma entrada 'd'. Permanecer nesse primeiro estado enquanto entrar 'a' e voltar ao 
estado final quando entrar um 'b'. Essa parte implica reconhecer c*+ da*b. Ocorre que 
para reconhecer apenas a cadeia a*b essa segunda parte tem que ser nula, daí a 
necessidade de se acrescentar um fecho de kleene na segunda expressão, resultando em: 
a*b(c + da*b)*. 
 
 
5a 
 Questão 
Acerto: 0,0 / 1,0 
 
A expressão regular que permite reconhecer a digitação correta de CEP no Brasil no 
modelo ddddd-ddd é: 
 
 ^\\d{5,5}\\-\\d{3,3}$ 
 
^\\d{3,5}\\-\\d{5,3}$ 
 
^\\d{5,5}\\-\\d{3,1}$ 
 ^\\d{5,1}\\-\\d{3,1}$ 
 
^\\d{3,3}\\-\\d{5,5}$ 
Respondido em 20/10/2022 09:57:31 
 
Explicação: 
Gabarito: ^\\d{5,5}\\-\\d{3,3}$ 
Justificativa: O padrão de CEP no Brasil é composto de 5 dígitos numéricos separados por 
um traço e mais três dígitos. A única alternativa que satisfaz esse padrão é a alternativa 
"^\\d{5,5}\\-\\d{3,3}$" 
 
 
6a 
 Questão 
Acerto: 1,0 / 1,0 
 
(POSCOMP / 2009 - adaptada) Seja o alfabeto Σ={a,b}Σ={a,b} e a linguagem 
regular L={ω|ω∈Σ∗e on°de a's emωé par}L={ω|ω∈Σ∗e on°de a's emωé par}. Qual 
das expressões regulares abaixo gera essa linguagem? 
 
 
( b* | ( a )* | b* )* 
 
(a b* b b*)* 
 ( b* a b* a b* )* 
 
( a | b )* 
 
( ( a )* | b* )* 
Respondido em 20/10/2022 09:58:34 
 
Explicação: 
Gabarito: ( b* a b* a b* )* 
Justificativa: Observe que a única alternativa em que se pode garantir que haverá a 
ocorrência de zero ou outro número par de 'a' é ( b* a b* a b* )*. Nas demais alternativas, 
sempre é possível gerar uma palavra com número ímpar de 'a'. 
 
 
7a 
 Questão 
Acerto: 0,0 / 1,0 
 
Seja a seguinte gramática S → aSa | bSb | a | b 
Palíndromos são cadeias do tipo wwr, ou seja, aqueles que lidos da esquerda para a 
direita ou vice e versa, são iguais. A linguagem gerada pela gramática acima sobre o 
alfabeto {a, b) é o conjunto de: 
 
 
Todos os palíndromos de comprimento par. 
 Cadeias que começam e terminam com símbolos diferentes. 
 
Todos os palíndromos. 
 Todos os palíndromos de comprimento ímpar. 
 
A gramática não gera palíndromos. 
Respondido em 20/10/2022 09:59:08 
 
Explicação: 
Gabarito: Todos os palíndromos de comprimento ímpar. 
Justificativa: Realizando algumas derivações como exemplo pode-se perceber que a 
alternativa b é a correta, por exemplo: S → aSa → S → aaa; S → aSa → S → abSba → 
ababa. 
 
 
8a 
 Questão 
Acerto: 1,0 / 1,0 
 
O que é verdadeiro para a seguinte GLC? 
S → aA | λ 
A → bA | a 
 
 
A produção nula pode ser removida. 
 
Como A não produz λ, λ não pode ser removido. 
 A produção nula não pode ser removida. 
 
Como A não produz λ, λ pode ser removido. 
 
Como S produz λ, λ pode ser removido. 
Respondido em 20/10/2022 10:00:11 
 
Explicação: 
Gabarito: A produção nula não pode ser removida. 
Justificativa: Se S pode ser derivado em λ, então a produção nula não pode ser removida. 
 
 
9a 
 Questão 
Acerto: 1,0 / 1,0 
 
O problema da parada para máquinas de Turing, ou simplesmente problema da parada, 
pode ser assim descrito: determinar, para qualquer máquina de Turing M e palavra w, 
se M irá eventualmente parar com entrada w. Mais informalmente, o mesmo problema 
também pode ser assim descrito: dados um algoritmo e uma entrada finita, decidir se o 
algoritmo termina ou se executará indefinidamente. Para o problema da parada: 
 
 
Existe algoritmo exato de tempo de execução exponencial para solucioná-lo. 
 
Existe algoritmo exato de tempo de execução polinomial para solucioná-lo. 
 Não existe algoritmo que o solucione, não importa quanto tempo seja 
disponibilizado. 
 
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de 
execução polinomial que o soluciona, fornecendo respostas aproximadas. 
 
Não existe algoritmo exato, mas existe algoritmo de aproximação de tempo de 
execução exponencial que o soluciona, fornecendo respostas aproximadas. 
Respondido em 20/10/2022 10:01:46 
 
Explicação: 
Não existe nenhuma máquina de Turing M que consiga decidir se vai parar ou entrar em 
loop infinito. O problema da parada é indecidível, portanto não existe algoritmo que o 
solucione. 
 
 
10a 
 Questão 
Acerto: 0,0 / 1,0 
 
Seja uma MT T dada pelas quíntuplas: 
1. (0, 1, 1, 0, D) 
 2. (0, b, 1, 1, H)Considere que 0 é um estado inicial e 1 é um estado final e a 
configuração inicial da fita igual a 111, com brancos antes e depois da cadeia 111 e n é 
o tamanho da cadeia, neste caso igual a 3. 
Qual a função que calcula essa MT? 
 
 
2n -1 
 2n +1 
 
2n 
 
2n+1 
 2n+1 - 1 
Respondido em 20/10/2022 10:04:49 
 
Explicação: 
Esse exemplo mostra o poder de computação das MT. Deve-se começar utilizando a 
quíntupla 1. Enquanto a MT ler 1 na fita, escreve 1, continua no estado 0 e anda para a 
direita (D). Ao encontrar um branco, escreve 1, muda para o estado final 1 e para (H). A 
cadeia final é 1111. A cadeia inicial era 111 = 23-1, foi transformada em 1111 = 24-1. Logo 
a MT calcula 2n+1 - 1