Decida se uma linguagem tem uma palavra de um determinado tamanho

Question

Suponha que $ l $ seja algum idioma sobre o alfabeto $ \ sigma $ . Fui convidado a mostrar que as seguintes línguas são decidíveis:

$$ l '={w \ in \ sigma ^ * | \ texto {existe uma palavra} w '\ em l \ text {tal que} | w' | \ leq | w | \} $$

ou seja, $ w \ in l '$ se $ l $ tem alguma palavra com comprimento menor do que $ | $ .

A maneira como eu estava pensando em mostrar que está observando que $ l \ cap \ sigma ^ {| w |} $ é finito, e $ (l \ Cap \ Sigma) \ Cup (l \ Cap \ Sigma ^ 2) \ Cup \ LDots \ Cup (l \ Cap \ Sigma ^ {| W |}) $ é finito também, portanto decidível. Mas a principal coisa que estou lutando é como qualquer algoritmo para $ l '$ sabe se alguma $ u \ in l $ ? Isso é indecável, por isso não está claro para mim como qualquer algoritmo para $ l '$ $ pode verificar que, de fato, alguma palavra está na $ L $

Answer 1

Existem dois casos:

.
1. $ l $ está vazio. Neste caso, $ l '=FORTSET $ é trivialmente decidível.
2. $ l $ não é vazio. Deixe $ m $ Seja o comprimento mínimo de uma palavra em $ l $ . Então $ l '$ consiste em todas as palavras de comprimento pelo menos $ m $ , e é novamente trivialmente decidível (em tempo constante!).

Como você pode ver, você nunca precisa realmente de um algoritmo para $ l $ .

---

.

Da mesma forma, a seguinte linguagem é sempre decidível:

$$ l ''= {w \ in \ sigma ^ * \ mid \ text {Existe uma palavra $ w '\ em l $ tal que $ | w' | \ geq | w | $}}. $$

Existem agora três casos:

.
1. $ l $ está vazio. Neste caso, $ l ''=FORTSET $ é trivialmente decidível.
2. $ l $ é infinito. Neste caso, $ l '=sigma ^ * $ é novamente triviall decidível.
3. $ l $ é finito. Deixe $ M $ o comprimento máximo de uma palavra na $ l $ . Então $ l '' $ consiste em todas as palavras de comprimento no máximo $ m $ e é novamente trivialmente Decidável (em tempo constante).

---

.

Estes são exemplos de provas não construtivas, que você pode não gostar. Em vez de começar uma discussão aqui, encamani-lo para esta questão .