Toda linguagem decidível $L$ tem um subconjunto decidível infinito $S \subset L$ tal que $L \setminus S$ é infinito
-
29-09-2020 - |
Pergunta
Dada uma linguagem decidível infinita $L$, então se $S \subconjunto L$ de tal modo que $L\setminus S$ é finito, então $S$ deve ser decidível.Isto é verdade, uma vez que dado um decisor de $L$ construímos um decisor para $S$:
Simular o decisor de $L$ na entrada, se aceitar, passe por cima $L\setminus S$ e verifique se está lá, se estiver, rejeite.Se não for aceite.Se o decisor de $L$ rejeita - rejeita.
Outro ponto é se $S \subconjunto L$ é finito então $S$ também deve ser decidível, é imediato que toda linguagem finita é decidível.
Agora temos o último caso em que $S$ é infinito e $L\setminus S$ é infinito.Sabemos que deve haver alguns subconjuntos $S$ correspondentes a este caso que são indecidíveis.Isto porque existem $\alef$ tal $S$ se apenas $\alef_0$ decisores.Denotar $D(L) = \{ S \subconjunto L :|S|= |L \setminus S|=\infty \wedge S ext{ é decidível} \}$
É verdade que para todas as linguagens infinitas decidíveis $L$ Nós temos $D(L) eq \phi$?
Se isso for verdade, então como conclusão teremos para todas as infinitas linguagens decidíveis $L$ uma sequência de linguagens decidíveis $L_n$ de tal modo que $L_0=L$ e $L_{n+1} \subconjunto L_n$ e $ | L_n setminus l_ {n+1} | = Infty $
Teremos também um limite definido $L_\infty = \{ e \in L :\forall n \in \mathbb{N} ext{ } e \in L_n \}$ e pode discutir se é vazio/finito/infinito e decicável ou não.
Esta parece ser uma boa maneira de estudar linguagens decidíveis, e curioso para saber se essa direção é realmente interessante e se existem artigos publicados sobre essas questões
Obrigado por qualquer ajuda
Solução
Se $L$ tem um alfabeto finito, então $L$ é recursivamente enumerável.
Então, a partir de tal enumeração $w_0,w_1,w_2,...$ das palavras de $L$ Tu podes levar $S=\{w_0,w_2,w_4,...\}$, que também será decidível.Para verificar se uma palavra $w$ é em $S$ verifique se está dentro $L$.Se for, então use a enumeração de $L$ para verificar se sua posição é par ou não.