Decida se uma linguagem tem uma palavra de um determinado tamanho
-
29-09-2020 - |
Pergunta
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 $
Solução
Existem dois casos:
- .
- $ l $ está vazio. Neste caso, $ l '=FORTSET $ é trivialmente decidível.
- $ 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!).
- $ l $ está vazio. Neste caso, $ l ''=FORTSET $ é trivialmente decidível.
- $ l $ é infinito. Neste caso, $ l '=sigma ^ * $ é novamente triviall decidível.
- $ 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).
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:
- .
.
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 .