LINGUAGENS FORMAIS, AUTÔMATOS E COMPILADORES EXERCÍCIO 02 (parte 4)

Prévia do material em texto

Acerto: 1,0 / 1,0
Com base nas afirmativas abaixo assinale a resposta correta:
I. Alfabeto ou vocabulário "V" é um conjunto finito e não vazio de símbolos.
II. Uma palavra sobre o alfabeto "V" é uma cadeia de comprimento finito de símbolos de "V".
III. Gramáticas são especificações infinitas de linguagens finitas.
IV. A classe das linguagens regulares é um subconjunto próprio da classe das linguagens livres de contexto.
I, II e III, apenas.
II e IV, apenas.
I e IV, apenas.
II e III, apenas.
 I, II e IV, apenas.
Respondido em 19/11/2022 17:45:23
 
 
Explicação:
Gabarito: I, II e IV, apenas.
Justificativa: Gramáticas são especificações finitas de linguagens infinitas. A afirmativa III está errada.
 
 
Acerto: 0,0 / 1,0
Gramáticas definem linguagens, sendo especificações finitas de regras de geração de cadeias. Nesse sentido,
assinale a alternativa incorreta.
a + b denota {a} U {b} = {a, b}
V U T = Σ
λ ∈ Σ*
 V ∩ T = ∅
 V ∩ T = Σ*
Respondido em 19/11/2022 18:17:12
 
 
Explicação:
Gabarito: V ∩ T = Σ*
Justificativa: Observe que V é o conjunto dos não terminais e T é o conjunto dos terminais. São dois conjuntos
disjuntos, logo sua intersecção é vazia. Todas as demais alternativas estão corretas.
 
 
Acerto: 0,0 / 1,0
Acerca dos conceitos de Computabilidade e Máquinas de Turing, assinale a alternativa INCORRETA.
Seja L uma linguagem recursivamente enumerável, se o complemento de L for recursivamente
enumerável, então L é uma linguagem recursiva.
 Um problema X é NP-completo quando X pertence à classe NP e, adicionalmente, X é redutível em
tempo polinomial para qualquer outro problema Y na classe NP.
Segundo a Tese de Church, a capacidade de computação representada pela máquina de Turing é o
limite máximo que pode ser atingido por qualquer modelo de computação.
 Todo problema que está na classe P também está na classe NP.
A união de duas linguagens recursivas é uma linguagem recursiva.
 Questão7
a
 Questão8
a
 Questão9
a