Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens da hierarquia de Chomsky e suas respectivas máquinas...

Acerca das características dos problemas decidíveis e indecidíveis e das diferentes linguagens da hierarquia de Chomsky e suas respectivas máquinas reconhecedoras, analise as afirmacoes a seguir e assinale a falsa.

Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G1) ∩ L(G2) = ∅, é indecidível.
Dadas duas gramáticas livres de contexto G1 e G2, é indecidível se L(G1) = L(G2).
O problema da parada de uma máquina de Turing é indecidível.
Nenhum procedimento computacional é considerado um algoritmo a menos que seja representado pela máquina de Turing.
É possível construir uma máquina de Turing que aceita qualquer cadeia de comprimento par.

Redes de Computadores

•

Colégio Objetivo

1

0

1

0

1

Estudando com Questões

17/06/2023

Essa pergunta também está no material:

4 pág.

Questões sobre Linguagens Formais e Autômatos

Redes de Computadores • Universidade Estácio de SáUniversidade Estácio de Sá

Leonardo sena

💡 1 Resposta

Ed

17.06.2023

A afirmativa falsa é: "Seja G1 qualquer gramática irrestrita e G2 seja qualquer gramática regular, então L(G1) ∩ L(G2) = ∅, é indecidível." Essa afirmativa é falsa porque a interseção entre uma linguagem livre de contexto e uma linguagem regular é uma linguagem livre de contexto. Portanto, é decidível verificar se a interseção entre uma linguagem livre de contexto e uma linguagem regular é vazia ou não.

0