6

Se temos uma linguagem L livre de contexto e seja L' um subconjunto de L, então L' é decidível?

2
  • 2
    Só para dar mais contexto para quem for responder, imagina que temos uma LLC L de parênteses: todo parêntese aberto precisa ser fechado e não posso fechar algo que não foi aberto. Isso significa que ((()())) é válido, porém ((())())) não é válido. Agora imagina que eu pego essa linguagem e removo todas as palavras que contenham (()) chamada L'; isso significa que ((())()) pertence a L, mas não a L', e ((()())) pertence a ambas Commented 15/10/2020 às 13:32
  • O comentário acima foi para ilustrar que precisamos lidar com remoções infinitas de L para obter L', esqueci de adicionar essa motivação no meu comentário Commented 15/10/2020 às 13:46

1 Resposta 1

7

Imagine que temos uma linguagem U que seja indecidível. As palavras dela pertencem ao alfabeto Σ. Se U existir, então ela é uma sublinguagem de Σ*.

Tomemos agora a seguinte gramática G que produza L(G):

S -> AS
S -> 
A -> el(Σ)

Onde el(Σ) é uma letra de Σ, qualquer uma. Essa linguagem equivale a Σ*. Portanto, se existir uma linguagem U para esse alfabeto, temos que U é subconjunto de L(G). E L(G) é uma linguagem regular, portanto também é uma linguagem livre de contexto.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .