Décider si une langue a un mot de taille donnée

Question

Supposons que $ l $ est une langue sur l'alphabet $ \ sigma $ . On m'a demandé de montrer que les langues suivantes sont décidables:

$$ l '={w \ in \ sigma ^ * | \ Text {Il existe un mot} w '\ in l \ texte {tel que} | w' | \ Leq | w | \} $$

c'est-à-dire, $ w \ in l '$ si $ l $ a quelques mots avec une longueur inférieure que $ | w | $ .

La façon dont je pensais montrer cela consiste à observer que $ l \ cap \ sigma ^ {| w |} $ est fini et $ (l \ cap \ sigma) \ tasse (l \ cap \ sigma ^ 2) \ tasse \ ldots \ tasse (l \ cap \ sigma ^ {| w |}) $ est fini aussi, donc décidable. Mais la principale chose dont je me lance, c'est comment tout algorithme pour $ l '$ savoir si une $ u \ in l $ ? Ceci est indécitable, il n'est donc pas clair pour moi de savoir comment tout algorithme pour $ l '$ peut vérifier que même certains mots sont en $ L $

Answer 1

Il y a deux cas:

1. $ l $ est vide. Dans ce cas, $ L '=ELTYSET $ est trivialement décembre.
2. $ l $ n'est pas vide. Laissez $ m $ être la longueur minimale d'un mot dans $ l $ . Alors $ l '$ se compose de tous les mots de longueur au moins $ m $ , et est à nouveau trivialement décritable (En temps constant!).

Comme vous pouvez le constater, vous n'avez jamais besoin d'un algorithme pour $ l $ .

---

De même, la langue suivante est toujours déterminable:

$$ l ''={w \ in \ sigma ^ \ \ \ mid \ text {Il existe un mot $ w "\ \ in li $ tel que $ | w ' | \ geq | w | $} \ \}. $$

Il y a maintenant trois cas:

1. $ l $ est vide. Dans ce cas, $ L ''=ELTYSET $ est trivialement décembre.
2. $ l $ est infini. Dans ce cas, $ l ''=sigma ^ * $ est à nouveau triviall.
3. $ l $ est fini. Laissez $ M $ être la longueur maximale d'un mot dans $ l $ . Alors $ l '' $ se compose de tous les mots de longueur au plus $ m $ , et est de nouveau trivialement décidable (en temps constant).

---

Ce sont des exemples de preuves non constructives que vous pourriez ne pas aimer. Au lieu de commencer une discussion ici, je vous réfère à cette question .