simulado 1 - LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES

Prévia do material em texto

Questão Acerto: 0,0  / 1,0
Referência: elaborado pelo autor, adaptado do livro Linz, Peter. An Introduction to Formal Languages 
and Automata, 6. Ed. Jones & Bartlett Learning, 2016.
 
Assinale a alternativa correta
a* = a+. a+
a* = a+. a*
  a+ = a*. a
a+ = a*. a*
  a = a + a
Respondido em 07/10/2022 14:26:37
Explicação:
De acordo com o fecho de Kleene, a* são todas as cadeias formadas por um número indeterminado de 
"a", incluindo a cadeia nula λ. Todas as cadeias formadas por um número indeterminado de "a", não 
incluindo a cadeia nula λ, é representado por a+. a+ é, exatamente, "a*.a", evitando que a cadeia nula 
venha a aparecer nessa linguagem.
          Questão Acerto: 1,0  / 1,0
Referência: elaborado pelo autor, 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 incluindo nulo
Qualquer combinação de a, b excluindo nulo
10a
Qualquer combinação de a, b, mas 'a' virá primeiro
Qualquer combinação de a, b, mas 'b' virá primeiro
λ
Respondido em 07/10/2022 14:27: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, 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)*
          Questão Acerto: 0,0  / 1,0
Considere as afirmativas abaixo e marque a única alternativa correta:
 
I. um conjunto finito e não vazio Σ de símbolos, é chamado de alfabeto.
II. A partir dos símbolos individuais nós construímos cadeias, que são sequências finitas ou infinitas de
símbolos do alfabeto, concatenados.
III. Uma linguagem formal é um conjunto, finito ou infinito, de cadeias, formadas pela concatenação 
de elementos de um alfabeto finito e não-vazio.
Apenas as alternativas II e III estão corretas
Apenas as alternativas I e II estão corretas
  Apenas a alternativa III está correta
Apenas a alternativa II está correta
  As alternativas I, II e III estão corretas
Respondido em 07/10/2022 14:28:53
Explicação:
Um alfabeto é um conjunto finito e não vazio de símbolos. Os símbolos formam as cadeias por meio da 
operação de concatenação. Um conjunto, finito ou infinito, de cadeias, formadas pela concatenação de 
elementos de um alfabeto finito e não-vazio é uma linguagem formal. De acordo com o exposto no texto, 
todas as alternativas estão corretas.
          Questão Acerto: 0,0  / 1,0
Dado que A = {x     | 1 < x < 3} e B = {x     | 2 < x < 20}, então A   B =∊ ∊ ∩ℕ ℕ
  { }
{3,4}
  {3}
{2,3}
{2}
Respondido em 07/10/2022 14:31:00
Explicação:
Gabarito: { }
Justificativa: O conjunto A = {2} e o conjunto B = {3..19}. Logo a intersecção de ambos é vazia, uma vez
que não há elementos comuns entre A e B
          Questão Acerto: 0,0  / 1,0
Analise as seguintes afirmativas.
I. Um Autômato Finito fornece o modelo mais simples de um dispositivo de computação.
II. A principal utilidade da teoria dos autômatos está no projeto do computador.
III. Um AF é um modelo matemático usado para representar programas de computador.
A análise permite concluir que
  Somente a afirmativa II é falsa.
Somente as afirmativas II e III são falsas.
Somente as afirmativas I e II são falsas.
Somente a afirmativa I é falsa.
  Somente a afirmativa III é falsa.
Respondido em 07/10/2022 14:33:33
Explicação:
Gabarito: Somente a afirmativa II é falsa.
Justificativa: A principal utilidade da teoria dos autômatos está no projeto do compilador.
          Questão Acerto: 1,0  / 1,0
Considere o autômato finito mostrado na figura abaixo (q0 é o estado inicial e q1 é o único estado 
final) e assinale a afirmativa correta.
 
  A palavra 010 é reconhecida pelo autômato.
Este é um autômato finito com saída.
A palavra 101011 é reconhecida pelo autômato.
A palavra 101 é reconhecida pelo autômato.
A palavra vazia é reconhecida pelo autômato.
Respondido em 07/10/2022 14:34:35
Explicação:
Gabarito: A palavra 010 é reconhecida pelo autômato.
Justificativa: Como o estado inicial é diferente do estado final, esse autômato não reconhece a palavra 
vazia. Este não é um autômato finito com saída porque as saídas não estão registradas na tabela. Esse 
autômato reconhece cadeias com um número impar de '1'.
          Questão Acerto: 0,0  / 1,0
O que é verdadeiro para a seguinte GLC?
S   aA | λ→
A   bA | a→
A produção nula pode ser removida.
Como S produz λ, λ pode ser removido.
  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.
Respondido em 07/10/2022 14:34:49
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.
          Questão Acerto: 0,0  / 1,0
Qual é a linguagem gerada pela gramática S   aSb, S   A, A   aA→ → →
  ∅
ambn
anbm
  ambm
ajbi
Respondido em 07/10/2022 14:35:30
Explicação:
Gabarito: ∅
Justificativa: As regras de produção não geram uma cadeia composta apenas de símbolos terminais. 
Portanto, a linguagem gerada é vazia.
          Questão Acerto: 1,0  / 1,0
Na classificação da hierarquia de Chomsky a gramática tipo 0 é uma gramática de estrutura de frase
sem   qualquer   restrição.   Dentro   dessa   hierarquia   estão   classificadas   a   linguagem   recursiva   e   a
linguagem   recursivamente   enumerável.   Acerca   de   suas   características   assinale   a   afirmação
verdadeira.
 
Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para 
sempre na entrada de uma máquina de Turing.
Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem 
recursiva.
  Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente 
enumerável.
Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
Respondido em 07/10/2022 14:36:01
Explicação:
As linguagens recursivas estão contidas no conjunto das linguagens recursivamente enumeráveis. 
Portanto, não são equivalentes. Uma linguagem recursiva é uma linguagem aceita por uma Máquina de 
Turing. Ambas as linguagens são aceitas por Máquinas de Turing. Quando uma linguagem é rejeitada a MT 
para, não entra em loop infinito.
          Questão Acerto: 1,0  / 1,0
Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo é 
quadrático, quanto tempo em segundos ele gastará, aproximadamente, no mesmo computador, se a 
entrada tiver tamanho 100?
20.
100.
500.
  40.
10.
Respondido em 07/10/2022 14:36:26
Explicação:
Como o algoritmo é quadrático, podemos fazer a seguinte aproximação para o tempo de execução: 
T(n)=cn2, onde c é uma constante a ser determinada. Sabe-se que T(50)=10, logo c*502 = 10 segundos, 
então 2500c=10 e determinamos c=1/250.  A expressão de complexidade de tempo para esse algoritmo é
T(n)=  (1/250) * n2. Logo, T(100) = (1/250)*1002.
T(100) = 10000/250 = 40.