Simulado Estácio Linguagens Formais Autômatos e Compiladores

Prévia do material em texto

1a 
 Questão 
Acerto: 0,0 / 1,0 
 
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. 
Ed. Jones & Bartlett Learning, 2016. 
 
Qual o tipo da seguinte gramática? 
 
S → aS/A 
aS → aa 
A → a 
 
 Sensível ao Contexto 
 Livre de Contexto 
 
Com estrutura de frase 
 
Regular 
 
Irrestrito 
Respondido em 07/10/2022 10:30:11 
 
Explicação: 
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção 
atendendo às seguintes restrições: 1. Todas as regras de produção devem ser do tipo (Não-
terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho 
do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 
1. A gramática do enunciado tem uma regra que torna sensível ao contexto, ao ter um 
símbolo não-terminal do lado esquerdo da produção. 
 
 
2a 
 Questão 
Acerto: 0,0 / 1,0 
 
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. 
Ed. Jones & Bartlett Learning, 2016. 
 
Qual o tipo da seguinte gramática: S → aSb e S → ab 
 
 Com estrutura de frase 
 
Irrestrito 
 
Regular 
 Livre de Contexto 
 
Sensível ao Contexto 
Respondido em 07/10/2022 10:31:03 
 
Explicação: 
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção 
atendendo às seguintes restrições: 1. Todas as regras de produção devem ser do tipo (Não-
terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho 
do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 
1. A gramática do enunciado atende a essas duas restrições. 
 
 
3a 
 Questão 
Acerto: 0,0 / 1,0 
 
Adaptado do livro Linz, Peter. An Introduction to Formal Languages and Automata, 6. 
Ed. Jones & Bartlett Learning, 2016. 
 
Qual é o maior número de tipo para a gramática dada pelas seguintes regras de 
produção S → Aa, A → c | Ba, B → abc. 
 
 
Zero 
 
Quatro 
 Dois 
 
Três 
 Um 
Respondido em 07/10/2022 10:36:36 
 
Explicação: 
Todas as gramáticas do tipo 2, livres de contexto, devem ter suas regras de produção 
atendendo às seguintes restrições: 1. Todas as regras de produção devem ser do tipo (Não-
terminal) → (Terminal ou qualquer combinação de terminal e não-terminal); 2. O tamanho 
do não-terminal do lado esquerdo da produção deve ser igual a 1, ou seja |Não-terminal| = 
1. A gramática do enunciado atende a essas duas restrições. 
 
 
4a 
 Questão 
Acerto: 0,0 / 1,0 
 
A expressão regular que permite reconhecer a digitação correta de CPF no Brasil é: 
 
 ^\\d{3}\\-\\d{3}\\-\\d{3}\\-\\d{2}$ 
 
^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{3}$ 
 
\\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2} 
 
^\\d{3}\\.\\d{3}\\.\\d{3}\\.\\d{2}$ 
 ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$ 
Respondido em 07/10/2022 10:31:51 
 
Explicação: 
Gabarito: ^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$ 
Justificativa: Sabemos que a expressão deverá iniciar com 3 dígitos separados por um 
ponto: ^\\d{3}\\. Devemos repetir três vezes esse padrão, colocar o separador "-", e mais 
dois dígitos verificadores. Lembrando que o '^' marca o início e o '$' o final da expressão 
regular. Assim, a expressão regular em Java para CPF será: 
^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{2}$ 
 
 
5a 
 Questão 
Acerto: 0,0 / 1,0 
 
(POSCOMP / 2013) Sobre o Lema do Bombeamento (pumping lemma) para linguagens 
regulares, considere as afirmativas a seguir. 
 
I. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do 
Bombeamento, que a linguagem L1 = {w ∈ Σ* | w termina com b} não é regular. 
II. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do 
Bombeamento, que a linguagem L2 = {(an)2 | n ≥ 1} não é regular. 
III. Se o alfabeto P = {a, b}, então pode-se provar por absurdo, por meio do 
Bombeamento, que as linguagens L3 = {an! | n ≥ 1}, L4 = {anbamban+m | n, m ≥ 1} e 
L5 = {am+1bn+1 | 2 ≤ n ≤ m ≤ 3n} não são regulares. 
IV. Se a linguagem for do tipo 3, então aplica-se o Bombeamento. 
 
Assinale a alternativa correta. 
 
 
Somente as afirmativas III e IV são corretas. 
 Somente as afirmativas II, III e IV são corretas. 
 Somente as afirmativas I e II são corretas. 
 
Somente as afirmativas I, II e III são corretas. 
 
Somente as afirmativas I e IV são corretas. 
Respondido em 07/10/2022 10:32:43 
 
Explicação: 
Gabarito: Somente as afirmativas II, III e IV são corretas. 
Justificativa: vamos aplicar o lema do bombeamento no item I. w é qualquer cadeia de 
'a' e 'b' que termina em b. Seja a cadeia w = abaab. Vamos dividir essa em três: x = 'a', y 
= 'ba' e z = 'ab'. Claramente o nosso comprimento de bombeamento é y = 2 ('ba') e p = 5. 
Assim vamos satisfazer as condições do lema: 
1. |y| ≥ 1 
2. |xy| ≤ p 
3. para todo i ≥ 0, xyiz ∈ L 
y é a subcadeia que pode ser bombeada (removida ou repetida arbitrariamente). 
Removendo y temos a cadeia aab que pertence a L1. Repetindo y duas vezes temos a 
cadeia ababaab que pertence a L1, uma vez que pertence a Σ* e termina em 'b'. É fácil 
perceber que a repetição de y dentro de w vai continuar satisfazendo a condição de 
pertencer a Σ* e terminar em 'b'. Portanto, não foi possível provar que L1 não é regular. 
Como o lema foi satisfeito para L1, então L pode ou não ser regular. Nada se pode afirmar 
e a afirmativa I é falsa. Todas as outras são verdadeiras 
 
 
6a 
 Questão 
Acerto: 0,0 / 1,0 
 
Considere o seguinte AF com saída 
 
A cadeia de saída desse AF para uma entrada 0011000 é: 
 
 
1000111 
 
0010000 
 0011000 
 1101111 
 
1111111 
Respondido em 07/10/2022 10:33:17 
 
Explicação: 
Gabarito: 1101111 
Justificativa: O AF lê o primeiro zero, permanece em q1 e emite um "1". Ao ler o segundo 
zero emite 1 e permanece em q1. O caractere seguinte é "1" ele e muda para o estado q2 e 
emite "0". No estado q2 lê o próximo "1", volta para o estado q1 e emite "1". No estado q1 
são lidos os caracteres "0" e o AF permanece em q1 emitindo a saída "1" por mais três 
vezes. 
 
 
7a 
 Questão 
Acerto: 0,0 / 1,0 
 
(POSCOMP / 2008) Considere as seguintes gramáticas: 
I II III IV 
A → bA 
A → aA 
A → ε 
B → BB 
B → b 
C → CaC 
A → AcA 
A → aca 
D → EE 
EE → FG 
F → a | aF 
G → b | bG 
A esse respeito, assinale a afirmativa FALSA: 
 
 A gramática II é livre de contexto. 
 A gramática IV é livre de contexto. 
 
A gramática III é livre de contexto. 
 
A gramática I é livre de contexto. 
 
Nenhuma das gramáticas é livre de contexto. 
Respondido em 07/10/2022 10:34:02 
 
Explicação: 
Gabarito: A gramática IV é livre de contexto. 
Justificativa: As gramáticas livres de contexto devem ter produções da forma: 
P = {A → β | A ∈ V ∧ β ∈ (V ∪ T)*} 
Claramente, a gramática IV tem produções que não estão no formato das gramáticas livres 
de contexto. As demais gramáticas têm todas as produções neste formato. 
 
 
8a 
 Questão 
Acerto: 1,0 / 1,0 
 
Considere a seguinte propriedade sobre uma linguagem formal L: ¿Existe um número 
natural n ≥ 0, tal que para qualquer palavra w ∈ L: 
1. Todo z ∈ L com z ≥ n pode ser escrito como w = uvwxy, para algumas cadeias 
u,v,w,x,y. 
2. |vx| ≥ 1 
3. |vwx| ≤ n 
4. uvkwxky ∈ L para todo k ≥ 0 
 
Com base no enunciado e nos conhecimentos sobre o tema, atribua V (verdadeiro) ou F 
(falso) para as afirmativas a seguir. 
• ( ) Se L é aceita por PDA, então L satisfaz a propriedade acima. 
• ( ) L = {0p; onde p é primo} não satisfaz a propriedade acima. 
• ( ) A propriedade acima é falsa para a linguagem L = {WcWR | W ∈ (a, b)*} 
• ( ) A linguagem {anbncn; n ≥ 0} não satisfaz a propriedade acima. 
• ( ) O lema do bombeamento para linguagem livre de contexto é usado para 
provar que certos conjuntos são livres de contexto. 
Assinale a alternativa que contém, de cima para baixo, a sequência correta: 
 
 
F, V, F, V, V. 
 
F, V, V, F, V. 
 
V, V, V, V, F. 
 V, V, F, V, F.V, F, V, F, F. 
Respondido em 07/10/2022 10:34:39 
 
Explicação: 
Gabarito: V, V, F, V, F. 
Justificativa: 
1. Esse é o lema do bombeamento para LLC e toda LLC é reconhecida por um PDA. 
2. Aplicando o lema é possível provar que 0p não é livre de contexto e não satisfaz a 
propriedade. 
3. WcWR é LLC, logo a propriedade é verdadeira e a afirmativa é falsa. 
4. Está correta conforme pode ser lido no Módulo 4, núcleo conceitual 1. 
5. O lema do bombeamento para linguagem livre de contexto é usado para provar que 
certos conjuntos não são livres de contexto. Alternativa falsa. 
 
 
9a 
 Questão 
Acerto: 1,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+1 
 2n+1 - 1 
 
2n 
Respondido em 07/10/2022 10:35:04 
 
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 
 
 
10a 
 Questão 
Acerto: 0,0 / 1,0 
 
A hierarquia de Chomsky representou um marco na classificação das linguagens e uma 
grande evolução para a computação. Acerca das características das diferentes 
linguagens e as respectivas máquinas reconhecedoras dessas linguagens, Aassinale a 
alternativa falsa. 
 
 
Toda Linguagem Regular é enumerável. 
 Todo Conjunto Finito é enumerável. 
 
O conjunto de todas as Expressões Regulares é enumerável. 
 
O conjunto de todas as Máquinas de Turing é enumerável. 
 Nenhum Conjunto Finito é enumerável. 
Respondido em 07/10/2022 10:35:56 
 
Explicação: 
Os conjuntos enumeráveis são os superconjuntos de todas as linguagens tratáveis por 
autômatos (no caso a máquina de Turing). Portanto, há linguagens infinitas cujas 
gramáticas são uma especificação finita e são enumeráreis e aceitas por Máquinas de 
Turing. Outo contraexemplo é o conjunto dos números naturais.