Logo Passei Direto
Buscar
5) Se c(M) é o código da máquina de Turing M. definimos as linguagens L₁ = {c(M) | L(M) é regular } e L₂ = {c(M) | L(M) é livre de contexto }. Assinale a alternativa verdadeira. Selecione uma alternativa: a) L₁ L₂ são recursivas. b) L₁ é recursiva e L₂ não é recursiva. LOLLUL₂ são recursivas Anterior Próxima 10:22 PT P4 01/10/2025​
User badge image
Gabriel Santos

ontem

Respostas

User badge image

Ed Verified user icon

ontem

Para responder a essa questão, precisamos entender as propriedades das linguagens regulares e livres de contexto em relação à decidibilidade. 1. Linguagens Regulares (L₁): A classe de linguagens regulares é decidível, ou seja, existe um algoritmo que pode determinar se uma dada máquina de Turing aceita uma linguagem regular. Portanto, L₁ é recursiva. 2. Linguagens Livres de Contexto (L₂): A classe de linguagens livres de contexto não é decidível em geral. Não existe um algoritmo que possa determinar se uma máquina de Turing aceita uma linguagem livre de contexto. Portanto, L₂ não é recursiva. Analisando as alternativas: a) L₁ e L₂ são recursivas. - FALSO, pois L₂ não é recursiva. b) L₁ é recursiva e L₂ não é recursiva. - VERDADEIRO, pois L₁ é recursiva e L₂ não é. c) L₁ e L₂ são recursivas. - FALSO, pela mesma razão da alternativa (a). Portanto, a alternativa correta é: b) L₁ é recursiva e L₂ não é recursiva.

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