Linguagens formais, autômatos e compiladores simulado 2

Prévia do material em texto

Meus
Simulados
Teste seu conhecimento acumulado
 
Disc.: LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES 
Acertos: 8,0 de 10,0
 
 
Acerto: 1,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
Regular
Irrestrito
Com estrutura de frase
Sensível ao Contexto
 Livre de 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: 1,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.
 Dois
Quatro
Zero
Um
Três
 
 
 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
Com estrutura de frase
Irrestrito
 Regular
 Sensível ao Contexto
Livre de 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: 1,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{2}$
^\\d{3}\\-\\d{3}\\-\\d{3}\\-\\d{2}$
^\\d{3}\\.\\d{3}\\.\\d{3}\\-\\d{3}$
\\d{2}\\.\\d{3}\\.\\d{3}\\-\\d{2}
 
 
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}$
 
 
 Questão3
a
 Questão4
a
Acerto: 1,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 II, III e IV são corretas.
Somente as afirmativas I e II são corretas.
Somente as afirmativas I e IV são corretas.
Somente as afirmativas III e IV são corretas.
Somente as afirmativas I, II e III são corretas.
 
 
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
 
 
Acerto: 1,0 / 1,0
Considere o seguinte AF com saída
A cadeia de saída desse AF para uma entrada 0011000 é:
0010000
1000111
 Questão5a
 Questão6
a
 1101111
1111111
0011000
 
 
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.
 
 
Acerto: 1,0 / 1,0
A diferença entre autômatos finitos e autômatos de pilha está na:
Direção do movimento da cabeça de leitura.
Fita de entrada.
Controle finito.
Cabeça de leitura.
 Pilha.
 
 
Explicação:
Gabarito: Pilha.
Justificativa: Os autômatos de Pilha são o formato de máquina de autômatos finitos para linguagens livres de
contexto. É um autômato finito com a anexação de uma quantidade auxiliar de armazenamento chamada de
pilha. A pilha é o componente do PDA que o diferencia dos autômatos finitos.
 
 
Acerto: 0,0 / 1,0
Uma linguagem L gerada a partir de uma dada GLC onde não existem ciclos no grafo direcionado gerado a
partir das regras de produção dessa GLC, é denominada de:
 Finita.
Recursiva.
Infinita.
Irrestrita (sem restrições).
 Sem contexto.
 
 
Explicação:
Gabarito: Finita.
Justificativa: Uma linguagem L gerada a partir de uma dada GLC é finita se não houver ciclos no grafo
direcionado gerado a partir das regras de produção dessa GLC.
 
 
Acerto: 1,0 / 1,0
 Questão7
a
 Questão8
a
 Questão
9a
Um cientista afirma ter encontrado uma redução polinomial de um problema NP-Completo para um problema
pertencente à classe P. Considerando que esta afirmação tem implicações importantes no que diz respeito à
complexidade computacional, avalie as seguintes asserções e a relação proposta entre elas.
I. A descoberta do cientista implica P = NP.
PORQUE
II. A descoberta do cientista implica na existência de algoritmos polinomiais para todos os problemas NP-
Completos.
 
A respeito dessas asserções, assinale a opção correta.
A asserção I é uma proposição verdadeira e a II é uma proposição verdadeira.
As asserções I e II são proposições verdadeiras, mas a II não é uma justificativa correta da I.
A asserção I é uma proposição falsa e a II é uma proposição verdadeira.
 As asserções I e II são proposições verdadeiras e a II é uma justificativa correta da I.
As asserções I e II são proposições falsas.
 
 
Explicação:
Sabemos que P ⊆ NP, ou seja, P é um subconjunto de NP. Problemas NP-completos são um conjunto de
problemas que podem ser reduzidos em tempo polinomial a partir de qualqueroutro problema NP, mas cuja
solução ainda pode ser verificada em tempo polinomial. Um problema NP-completo é pelo menos tão difícil
quanto qualquer outro problema NP. Para esse caso hipotético, por redução, implica que P=NP e a asserção I é
verdadeira. Uma vez que P=NP, existem algoritmos polinomiais para todos os problemas NP e a proposição II é
verdadeira e uma justificativa da I.
 
 
Acerto: 1,0 / 1,0
Com base nas afirmativas abaixo sobre a descrição instantânea (DI) da máquina de Turing assinale a resposta
correta:
 
I. Lembra o estado da máquina.
II. Lembra da célula que está sendo digitalizada pelo cabeçote de leitura e gravação.
III. O conteúdo de todas as células da fita.
IV. O conteúdo da célula seguinte a que está sendo lida.
II e III, apenas
I e IV, apenas.
 I, II e III, apenas
I, II e IV, apenas
II e IV, apenas
 
 
Explicação:
Não há como a cabeça de leitura saber o que está na célula seguinte a ser lida. Esta afirmativa está errada. As
demais estão corretas conforme a definição de Descrição Instantânea.
 
 
 
 Questão10
a
javascript:abre_colabore('38403','296527498','5804251548');