NAV- LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES

Prévia do material em texto

Considere as seguintes regras de gramática, onde "|" representa "ou", λ representa a cadeia vazia e
undrscr é o caractere "_".
 
1. →
2. → 
3. →
4. → 
5. → 
6. → λ
7. a | b | ... | z | A | B | ... | Z→
8. 0 | 1 | ... | 9→
9. _→
 
Assinale a cadeia que pode ser gerada pela aplicação das produções na seguinte ordem:1, 7, 3, 7, 5,
9, 4, 8, 6
a0
  ab_9
_ab9
ab_
7b1
Respondido em 19/11/2022 14:58:51
Explicação:
Sabemos que as cadeias são geradas a partir do emprego das regras de produção. Aplicando a regra 1 
temos . Na sequência aplica-se a regra 7 onde foi substituída por uma letra, portanto, fica estabelecido ⇒
que essa cadeia irá iniciar por uma letra, o que já elimina as alternativas "d" e "e". Neste ponto estamos 
em a, supondo que a letra que foi substituída é "a" já que todas as alternativas iniciam com a letra "a". Em
seguida, é aplicada a regra 3 e ficamos com a cadeia a< resto >.
Aplicando a regra 7 substituímos a por "b", o que elimina a alternativa "b". Neste ponto estamos com a 
cadeia ab. Aplicando a regra 5 ficamos com ab . Pela regra 9 geramos ab_. Pela regra 4 ab_. A regra 8 
aplicada gera ab_9, ou qualquer outro dígito, mas para o caso em questão nos interessa o 9.
Ao aplicar a regra 6 substituímos pela cadeia nula (λ) e geramos ab_9.
As produções podem ser desenvolvidas como segue:
10a
⇒⇒a a ab ab⇒ ⇒ ⇒
⇒ab_ ab_ ab_9.⇒ ⇒
          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 a linguagem gerada pela gramática: G = {(S, A), (0, 1), (S 0S1, S A, A 0A), S}.→ → →
1m0n
0m1m
0m1n
  1m0m
  λ
Respondido em 19/11/2022 15:03:02
Explicação:
Observe que não existe uma regra de produção que possa nos levar a um símbolo terminal apenas. Todas 
as regras de produção, se aplicadas, nos levam a cadeias compostas de terminais e não terminais. Sendo 
impossível gerar cadeias formadas apenas de terminais, essa é uma linguagem vazia.
          Questão Acerto: 0,0 / 1,0
Considere, a seguir, a gramática livre de contexto G = (V, T, P, S), onde V = {S}, T = {a,b,c}, e P:
S aS|Sb|c→
Qual expressão regular gera a mesma linguagem que a gramática definida acima?
  an c bm, onde n, m ≥ 0
ca+ b+
  anc bn, onde n ≥ 0
a+ b+ c
an c bm, onde n, m ≥ 1
Respondido em 19/11/2022 15:04:02
Explicação:
Aplicando algumas regras de produção podemos inferir a lei geral de formação de cadeias dessa 
linguagem. S c. Isso equivale a λcλ. Logo n, m ≥ 0, eliminamos as alternativas de a) até c), uma vez →
que pode haver cadeias sem símbolos ¿a¿ e/ou ¿b¿. Sejam os exemplos: S aS ac e S Sb cb. Esses → →⇒ ⇒
dois exemplos nos mostram que as cadeias dessa linguagem podem ter números diferentes de símbolos 
¿a¿ e ¿b¿, indicando que a alternativa d está errada.
          Questão Acerto: 0,0 / 1,0
Dado que A = {x | 1 < x < 3} e B = {x | 2 < x < 20}, então A B =∊ ∊ ∩ℕ ℕ
  { }
{2,3}
{3,4}
  {3}
{2}
Respondido em 19/11/2022 15:04:19
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 19/11/2022 15:06: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 101 é reconhecida pelo autômato.
Este é um autômato finito com saída.
A palavra vazia é reconhecida pelo autômato.
A palavra 101011 é reconhecida pelo autômato.
  A palavra 010 é reconhecida pelo autômato.
Respondido em 19/11/2022 15:00:11
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: 1,0 / 1,0
Alguns tipos de símbolos e produções aumentam o número de etapas na geração de uma linguagem a 
partir de uma GLC. Nesse sentido, símbolos inúteis em uma Gramática Livre de Contexto são:
Produções nulas.
Símbolos não terminais.
Alfabetos nulos.
  Símbolos não geradores e símbolos não alcançáveis.
Cadeia nula.
Respondido em 19/11/2022 15:07:15
Explicação:
Gabarito: Símbolos não geradores e símbolos não alcançáveis.
Justificativa: Os dois tipos de símbolos inúteis incluem os símbolos não geradores, aqueles símbolos que 
não produzem nenhuma cadeia terminal, e os símbolos não alcançáveis, aqueles símbolos que não podem 
ser alcançados a qualquer momento a partir do símbolo inicial. Toda linguagem livre de contexto pode ser 
gerada por uma gramática livre de contexto em que não há símbolos inacessíveis ou inúteis.
          Questão Acerto: 0,0 / 1,0
Avalie as proposições (1) e (2) a seguir:
(1) Uma linguagem L gerada a partir de uma dada GLC é infinita
(2) se houver pelo menos um ciclo no grafo direcionado gerado a partir das regras de produção dessa 
GLC
A esse respeito, assinale a afirmativa VERDADEIRA.
A proposição (1) é verdadeira e (2) é falsa.
Ambas as proposições são falsas.
As proposições (1) e (2) são verdadeiras, sendo que a (1) justifica a (2).
  As proposições (1) e (2) são verdadeiras, sendo que a (2) justifica a (1).
  As proposições (1) e (2) são verdadeiras, sendo que a (2) não justifica a (1).
Respondido em 19/11/2022 15:08:19
Explicação:
Gabarito: As proposições (1) e (2) são verdadeiras, sendo que a (2) não justifica a (1).
Justificativa: Uma linguagem L gerada a partir de uma dada GLC é infinita se houver pelo menos um ciclo 
no grafo direcionado gerado a partir das regras de produção dessa GLC.
          Questão Acerto: 1,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.
Todo Conjunto Finito é enumerável.
  Nenhum Conjunto Finito é enumerável.
O conjunto de todas as Máquinas de Turing é enumerável.
O conjunto de todas as Expressões Regulares é enumerável.
Toda Linguagem Regular é enumerável.
Respondido em 19/11/2022 15:14:12
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.
          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?
  40.
20.
10.
100.
500.
Respondido em 19/11/2022 15:15:22
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.