Logo Passei Direto
Buscar
Se c(M) é o código da máquina de Turing M, definimos as linguagens L₁ = {c(M) | L(M) é regular } e L2 = {c(M) | L(M) é livre de contexto }. Assinale a alternativa verdadeira. Selecione uma alternativa: a) L₁ e L2 são recursivas. b) L1 é recursiva e L2 não é recursiva. c) L₁ CL2. Od) L2 CL1- Oe) L1 L2 e L1 U L2 são recursivas.
User badge image
Luiz Otávio

anteontem

Respostas

User badge image

Ed Verified user icon

anteontem

Para responder a essa questão, precisamos entender as propriedades das linguagens regulares e livres de contexto em relação às máquinas de Turing. 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. Agora, 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₁ ⊆ L₂. - FALSO, pois L₁ contém linguagens que não estão em L₂. d) L₂ ⊆ L₁. - FALSO, pois L₂ contém linguagens que não são regulares. e) L₁ e L₂ e L₁ ∪ L₂ são recursivas. - FALSO, pois L₂ não é recursiva. 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