Linguagens formais, autômatos e compiladores, simulado 1

Prévia do material em texto

Meus
Simulados
Teste seu conhecimento acumulado
 
Disc.: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES 
Acertos: 1,0 de 10,0
 
 
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
 Livre de Contexto
Com estrutura de frase
Irrestrito
 Regular
Sensível ao Contexto
 
 
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.
 
 
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.
Três
 Um
Quatro
 Dois
Zero
 
 
 Questão1
a
 Questão2
a
https://simulado.estacio.br/alunos/inicio.asp
javascript:voltar();
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.
 
 
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
 Irrestrito
Livre de Contexto
Regular
Com estrutura de frase
 Sensível ao Contexto
 
 
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.
 
 
Acerto: 0,0 / 1,0
(POSCOMP / 2009) A análise léxica é usualmente implementada a partir de:
Gramática livre de contexto.
 Gramática regular.
 Gramática sensível ao contexto.
Gramática de pilha.
Gramática irrestrita.
 
 
Explicação:
Gabarito: Gramática regular.
Justificativa: A primeira fase do compilador chamada analisador léxico é projetada pelos autômatos
finitos, que são os reconhecedores das expressões regulares geradas pelas gramáticas regulares.
 
 
Acerto: 0,0 / 1,0
 Questão3
a
 Questão4
a
 Questão5
a
Com base nas afirmativas abaixo assinale a resposta correta:
I. As Linguagens Regulares podem ser geradas por gramáticas regulares e reconhecidas por autômatos
finitos.
II. Com base na hierarquia de Chomsky as linguagens regulares são as de tipo 0.
III. Em todo autômato finito existe sempre um estado inicial fixo.
IV. Gramáticas têm um número finito de regras de produção.
I e IV, apenas.
I, II e IV, apenas
 I, III e IV, apenas
 II e IV, apenas
II e III, apenas
 
 
Explicação:
Gabarito: I, III e IV, apenas
Justificativa: As linguagens regulares são as do tipo 3 e não do tipo 0. As demais alternativas estão corretas.
 
 
Acerto: 1,0 / 1,0
(POSCOMP / 2008) Considere o autômato finito mostrado na figura abaixo (os círculos em negrito representam
estados terminais)
A esse respeito, assinale a afirmativa FALSA.
A palavra ababa não é reconhecida pelo autômato.
 A palavra aba é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
A palavra baba é reconhecida pelo autômato.
A palavra aaa é reconhecida pelo autômato.
 
 
Explicação:
Gabarito: A palavra aba é reconhecida pelo autômato.
Justificativa: Esse AFN realiza uma transição em ε para um estado final, logo reconhece a palavra vazia. Essa
mesma transição permite o reconhecimento de baba. Existe um caminho para o reconhecimento de aaa e ababa
não é reconhecida. Logo, todas essas alternativas são verdadeiras. A palavra aba não é reconhecida pelo
autômato porque não há caminhos que levem a um estado final. Essa alternativa é falsa.
 
 
Acerto: 0,0 / 1,0
Em relação a autômatos e linguagens, podemos afirmar:
I. PDA é o formato de máquina de linguagem livre de contexto.
 Questão6
a
 Questão7
a
II. A descrição instantânea do PDA descreve a configuração dele em uma determinada instância.
III. Uma cadeia de uma LLC pode ser aceita por pilha vazia ou pelo estado final.
É correto apenas o que se afirma em:
 I, II e III
I
 II e III
II
I e III
 
 
Explicação:
Gabarito: I, II e III
Justificativa: Os autômatos de Pilha (PDA) são o formato de máquina de autômatos finitos para linguagens
livres de contexto. A Descrição Instantânea descreve a configuração do PDA em uma determinada instância,
onde o ID lembra as informações do estado e o conteúdo da pilha em uma determinada instância de tempo.
Uma cadeia w (LLC) pode ser declarada aceita por uma pilha vazia se, após o processamento de todos os
símbolos de w, a pilha estiver vazia. Uma cadeia w pode ser declarada aceita pelo estado final se, após a
passagem total da cadeia w, o PDA entrar em um estado final.
 
 
Acerto: 0,0 / 1,0
O que é verdadeiro para a seguinte GLC?
S → aA | λ
A → bA | a
A produção nula pode ser removida.
 A produção nula não pode ser removida.
Como A não produz λ, λ pode ser removido.
Como S produz λ, λ pode ser removido.
 Como A não produz λ, λ não pode ser removido.
 
 
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.
 
 
Acerto: 0,0 / 1,0
Na máquina de Turing, a função de transição δ está na forma:(onde Q é o conjunto finito de estados, Σ é o
conjunto finito de alfabetos de entrada, Γ é o símbolo de fita permitido, L significa esquerda, R significa direita
e H significa parada).
Q × Γ → (Q × Σ × {H})
Q ×Σ→ (Q × Σ × {L, R, H})
Q × Γ → (Q × Σ)
 Q × Γ → (Q × Γ × {L, R, H})
 Q ×Σ→ (Q × {L, R, H})
 
 Questão8
a
 Questão9
a
 
Explicação:
A função de transição de estados para MT é definida como um produto cartesiano de Q × Γ, onde Γ é alfabeto
da fita, levando em uma imagem definida por outro produto cartesiano de Q × Γ multiplicado pelas ações da
máquina em seguir para a esquerda, direita ou parar {L, R, H}.
 
 
Acerto: 0,0 / 1,0
Para resolver problemas, precisamos construir algoritmos. Para esses algoritmos, suas complexidades
precisam ser calculadas, as quais são necessárias para analisar os algoritmos e encontrar o mais adequado. 
Considere as seguintes quatro funções:
f1 (n) = 2n
f2 (n) = n2
f3 (n) = 2n2
f4 (n) = 2n + 3
 
Quais das seguintes sentenças matemáticas são verdadeiras?
I. para n > 0, f2 (n) < f3 (n)
II. para n > 2, f1 (n) < f2 (n)
III. para n = 0, f2 (n) < f3 (n)
IV. para n < 2, f1 (n) < f2 (n)
V. para n > 2, f3 (n) < f4 (n)
 
somente II, III e IV.
somente III, IV e V.
 somente I, III e IV.
 somente I, II e V.
somente I e II.
 
 
Explicação:
Consideremos a seguinte tabela:
Função n = 0 n = 2 n = 10 n = 20
f1(n) 0 4 20 40
f2(n) 0 4 100 400
f3(n) 0 8 200 800
f4(n) 4 7 1027 1.048.579
 
É fácil observar que para n = 0, f2 (n) = f3 (n) = 0 e que para n < 2, f1 (n) = f2 (n) = 0, logo são falsas; as
sentenças I, II e V são verdadeiras.
 
 
 
 Questão10
a
javascript:abre_colabore('38403','299773169','5941857997');