Gabarito: Alternativa C - II e IV, apenas.

Vamos analisar cada uma das afirmativas para entender por que a alternativa C é a correta:

Tema Central: A questão aborda conceitos fundamentais relacionados às Máquinas de Turing e tipos de linguagens no contexto da Teoria da Computação. Esses conceitos são essenciais para compreender os limites do que pode ser computado e como diferentes classes de linguagens são reconhecidas.

Afirmação I: Toda linguagem recursivamente enumerável é também uma linguagem regular, pois pode ser aceita por uma máquina de Turing não-determinística.

Errada - Linguagens recursivamente enumeráveis são mais gerais que linguagens regulares. Uma linguagem regular pode ser aceita por um autômato finito, enquanto uma linguagem recursivamente enumerável requer uma Máquina de Turing para reconhecimento, ou seja, nem toda linguagem recursivamente enumerável é regular. (Referência: "Introduction to the Theory of Computation", Michael Sipser)

Afirmação II: A união de duas linguagens recursivas é uma linguagem recursiva.

Correta - Linguagens recursivas são fechadas sob operações como união, interseção e complementação. Portanto, a união de duas linguagens recursivas resulta em uma linguagem recursiva. (Referência: "Introduction to Automata Theory, Languages, and Computation", Hopcroft, Motwani, Ullman)

Afirmação III: O problema da parada pode ser resolvido por uma máquina de Turing determinística, desde que tenha uma quantidade de fita infinita disponível.

Errada - O problema da parada é um problema clássico da computação que é intrinsecamente não decidível por qualquer Máquina de Turing, independentemente de ser determinística ou ter fita infinita. (Referência: "The Annotated Turing", Charles Petzold)

Afirmação IV: Toda linguagem recursiva também é recursivamente enumerável.

Correta - Linguagens recursivas são um subconjunto das linguagens recursivamente enumeráveis, o que significa que qualquer linguagem recursiva será, por definição, recursivamente enumerável. (Referência: "Theory of Computation", Dexter Kozen)

Com isso, verificamos que as afirmativas corretas são II e IV, conferindo que a alternativa C está correta.

Gostou do comentário? Deixe sua avaliação aqui embaixo!