Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — IF-MG 2024

Algoritmos e Estrutura de DadosAlgoritmos
Código
qg240031
Banca
IF-MG
Órgão
IF-MG
Ano
2024
Nível
Superior
Cargo
PROFESSOR EBTT - Ciência da Computação e Sistemas de Informação. - Ribeirão das Neves
Analise as afirmativas abaixo sobre Máquina de Turing e linguagens: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.II. A união de duas linguagens recursivas é uma linguagem recursiva.III. 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.IV. Toda linguagem recursiva também é recursivamente enumerável.Está(ão) correta(s) a(s) afirmação(ões):
  1. AI, e II, apenas
  2. BIII, IV, apenas.
  3. CII e IV, apenas.
  4. DI, II e IV, apenas
  5. EI, II, III e IV.
Revelar gabarito e comentário

GabaritoC — II e IV, apenas.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Máquina de Turing e Linguagens Formais

Gabarito: letra C (itens II e IV corretos). A questão testa a hierarquia das classes de linguagens e propriedades de fechamento. Itens II e IV estão corretos; os itens I e III contêm erros conceituais clássicos.

RecursivasRecursivamente EnumeráveisII, IVI, IIIII, IVLEVELsoulevel.com.br
Linguagens Recursivas e RE — só Recursivas: II, IV; só Recursivamente Enumeráveis: I, III; Recursivas∩Recursivamente Enumeráveis: II, IV

Item I — ❌ Incorreto

A afirmativa inverte a hierarquia: linguagens recursivamente enumeráveis (RE) são a classe mais ampla (aceitas por MT não-determinística), enquanto linguagens regulares são um subconjunto próprio das RE. Existem linguagens RE que não são regulares (ex.: {aⁿbⁿ | n ≥ 0} é livre de contexto, não regular). Portanto, a implicação "toda RE é regular" é falsa.

Item II — ✅ Correto

Linguagens recursivas (decidíveis) são fechadas sob união. Se L₁ e L₂ são decidíveis, existe uma MT que decide L₁ e outra que decide L₂; pode-se construir uma MT que decide L₁ ∪ L₂ (simular ambas em paralelo e aceitar se qualquer uma aceitar). Logo, a união é recursiva.

Item III — ❌ Incorreto

O problema da parada é indecidível, independentemente da quantidade de fita disponível. A indecidibilidade é inerente ao problema, não uma limitação de recursos. Mesmo com fita infinita, não existe MT determinística que resolva a parada para todas as entradas (prova de Turing, 1936).

Item IV — ✅ Correto

Toda linguagem recursiva é também recursivamente enumerável. Se uma linguagem é decidível (recursiva), ela é trivialmente semi-decidível (RE), pois a MT que a decide também a aceita (para toda entrada ela para, e aceita as palavras da linguagem).

Conclusão: Corretos apenas II e IV → alternativa C.

Link permanente: /questoes/qg240031