Logo Passei Direto
Buscar
Na classificação da hierarquia de Chomsky, a gramática tipo Oé 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. A Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável. B Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva. Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre C na entrada de uma máquina de Turing. D Uma linguagem recursiva e uma recursivamente enumerável são equivalentes. F Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing.
User badge image
Maria Eduarda Lopes Diniz

há 4 dias

Respostas

User badge image

Ed Verified user icon

há 4 dias

Vamos analisar cada uma das afirmações sobre linguagens recursivas e recursivamente enumeráveis: A) Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável. Verdadeiro. Toda linguagem recursiva é, de fato, um subconjunto das linguagens recursivamente enumeráveis, pois as linguagens recursivas são aquelas que podem ser decididas por uma máquina de Turing que sempre para. B) Uma linguagem recursivamente enumerável é um subconjunto de uma linguagem recursiva. Falso. Linguagens recursivamente enumeráveis podem não ser decidíveis, ou seja, podem não ser recursivas. C) Uma linguagem recursiva e uma recursivamente enumerável podem fazer um loop para sempre na entrada de uma máquina de Turing. Falso. Apenas linguagens recursivamente enumeráveis podem fazer um loop para sempre, enquanto as linguagens recursivas sempre terminam. D) Uma linguagem recursiva e uma recursivamente enumerável são equivalentes. Falso. Como mencionado, as linguagens recursivas são um subconjunto das recursivamente enumeráveis, mas não são equivalentes. F) Uma linguagem recursiva é uma linguagem que não é aceita por uma Máquina de Turing. Falso. Na verdade, uma linguagem recursiva é aceita por uma Máquina de Turing que sempre para. Portanto, a afirmação verdadeira é a alternativa A: "Uma linguagem recursiva é um subconjunto de uma linguagem recursivamente enumerável."

Essa resposta te ajudou?

0
Dislike0

Ainda com dúvidas?

Envie uma pergunta e tenha sua dúvida de estudo respondida!

Mais conteúdos dessa disciplina