Se temos uma linguagem L livre de contexto e seja L' um subconjunto de L, então L' é decidível?
1 Resposta
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.
((()()))
é 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