Решить, имеет ли язык слова данного размера

Question

Предположим, что $ l $ - это какой-то язык через алфавит $ \ sigma $ . Меня попросили показать, что следующие языки являются разрешенными:

$$ l '={w \ in \ sigma ^ * | \ Text {существует слово} w '\ in l \ text {такая, что} | w' | \ leq | w | \} $$

IE, $ W \ in l '$ Если $ l $ имеет некоторое слово с длиной меньше Чем $ | w | $ .

То, как я думал показать, что это наблюдает, что $ l \ cap \ sigma ^ {| w |} $ конечно, и $ (l \ cap \ sigma) \ cup (l \ cap \ sigma ^ 2) \ cup \ ldots \ cub (l \ cap \ sigma ^ {| w |}) $ конечно тоже, следовательно, решительно. Но главное, с которым я могу быть, это как любой алгоритм для $ l '$ знаю, если некоторые $ u \ in l $ ? Это неразрешимо, поэтому для меня неясно, как любой алгоритм для $ l '$ может убедиться, что действительно некоторое слово находится в $ L $

Answer 1

Есть два случая:

1. $ l $ пустой. В этом случае $ l '=emptyset $ тривиально разрешимо.
2. $ l $ не пусто. Пусть $ m $ - минимальная длина слова в $ l $ . Тогда $ L '$ состоит из всех слов длины, по крайней мере, $ m $ , и снова тривиально решительно (в постоянном времени!).

Как вы можете видеть, вам никогда не нужен алгоритм для $ l $ .

---

Точно так же, следующий язык всегда разрешен:

$$ l ''={w \ in \ sigma ^ * \ \ mid \ text {Существует слово $ w '\ in l $ такая, что $ | w' |. \ geq | w | $} \}. $$

Сейчас есть три случая:

1. $ l $ пустой. В этом случае $ l ''=emptyset $ тривиально разрешит.
2. $ l $ бесконечно. В этом случае $ L ''=Sigma ^ * $ опять тривиаль, разрешимый.
3. $ l $ конечно. Пусть $ m $ - максимальная длина слова в $ l $ . Затем $ L '' $ состоит из всех слов длины на большинстве $ m $ , и снова имеет тривиально решительно (в постоянное время).

---

Это примеры неконструктивных доказательств, которые вы можете не понравиться. Вместо того, чтобы начать обсуждение здесь, я ссылаюсь на вас в этот вопрос .