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 ...
Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
Uma linguagem recursiva e uma recursivamente enumerável são equivalentes.
Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre na entrada de uma máquina de Turing.
Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável.
Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva.
Essa pergunta também está no material:
💡 1 Resposta
Ed 
A afirmação verdadeira é: "Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável." Uma linguagem recursiva é uma linguagem que pode ser reconhecida por uma Máquina de Turing, ou seja, é uma linguagem que pode ser decidida por um algoritmo. Já uma linguagem recursivamente enumerável é uma linguagem que pode ser gerada por uma gramática tipo 0, mas não necessariamente pode ser decidida por um algoritmo. Como toda linguagem recursiva pode ser gerada por uma gramática tipo 0, ela também é uma linguagem recursivamente enumerável. Portanto, a afirmação "Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável" é verdadeira.
Faça como milhares de estudantes: teste grátis o Passei Direto
Esse e outros conteúdos desbloqueados
16 milhões de materiais de várias disciplinas
Impressão de materiais
Agora você pode testar o
Passei Direto grátis
✏️ Responder
Para escrever sua resposta aqui, entre ou crie uma conta
Outros materiais
Perguntas relacionadas
Materiais relacionados
Compartilhar