Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCM 2018

Linguagens Recursivas e Recursivamente Enumeráveis

Gabarito: letra E. A classe das linguagens recursivas é um subconjunto estrito da classe das linguagens recursivamente enumeráveis, pois toda linguagem recursiva é RE, mas existem linguagens RE que não são recursivas (ex: problema da parada). Esse é um resultado fundamental da teoria da computação, decorrente da definição de Máquina de Turing (MT): uma linguagem é recursiva se existe uma MT que sempre para e decide a pertinência; é RE se existe uma MT que aceita as strings do conjunto (podendo não parar para as demais).

A questão testa o conhecimento das relações entre classes de linguagens na hierarquia de Chomsky e propriedades de fechamento.

Alternativa A — ❌ Incorreta

Afirma que um autômato finito pode reconhecer uma linguagem recursiva se o alfabeto for grande. Autômatos finitos reconhecem apenas linguagens regulares, que são um subconjunto próprio das recursivas. O tamanho do alfabeto não altera o poder computacional; a capacidade de reconhecimento de linguagens recursivas requer uma Máquina de Turing, não um autômato finito.

Alternativa B — ❌ Incorreta

Diz que uma linguagem é RE se e somente se é livre de contexto e regular. Isso é falso: as classes regulares e livres de contexto são subconjuntos próprios das RE, mas há linguagens RE que não são nem regulares nem livres de contexto (ex: linguagens recursivamente enumeráveis indecidíveis). A relação correta na hierarquia de Chomsky é: regular ⊂ livre de contexto ⊂ recursiva ⊂ RE.

Alternativa C — ❌ Incorreta

Afirma que as classes recursiva e RE são equivalentes. Não são: existem linguagens RE que não são recursivas (indecidíveis). A classe recursiva é um subconjunto próprio da RE.

Alternativa D — ❌ Incorreta

Afirma que a classe RE é fechada sob complemento. Isso é falso: se uma linguagem e seu complemento fossem ambos RE, a linguagem seria recursiva (teorema). Como existem linguagens RE não recursivas (ex: problema da parada), o complemento de uma linguagem RE não é necessariamente RE. A classe recursiva, sim, é fechada sob complemento.

Alternativa E — ✅ Correta ⟵ GABARITO

A classe das linguagens recursivas é subconjunto estrito das RE. Toda linguagem recursiva é RE (pois uma MT que sempre para aceita as strings e rejeita as demais, funcionando como aceitadora), e existem linguagens RE que não são recursivas (a própria indecidibilidade do problema da parada). Portanto, a inclusão é própria e estrita.

Gabarito: letra E