Decide si un idioma tiene una palabra de un tamaño determinado

Question

Supongamos que $ l $ es algún idioma sobre el alfabeto $ \ sigma $ . Me pidieron que demostrara que los siguientes idiomas son decidibles:

$$ l '={w \ in \ sigma ^ * | \ Texto {existe una palabra} w '\ in l \ text {tal que} | w' | \ leq | w | \} $$

IE, $ w \ in l '$ si $ l $ tiene alguna palabra con la longitud más pequeña que $ | w | $ .

La forma en que estaba pensando en demostrar que está observando que $ l \ cap \ sigma ^ {| w |} $ es finito, y $ (l \ cap \ sigma) \ CUP (l \ cap \ sigma ^ 2) \ Cup \ ldots \ Cup (l \ cap \ sigma ^ {| w |}) $ es finito También, por lo tanto, decidible. Pero lo principal con lo que estoy luchando es cómo puede cualquier algoritmo para $ l '$ saber si algunos $ u \ en l $ ? Esto no es decidible, por lo que no me está claro cómo cualquier algoritmo para $ l '$ puede verificar que, de hecho, alguna palabra está en $ L $

Answer 1

Hay dos casos:

1. $ l $ está vacío. En este caso, $ l '=vacioset $ es trivialmente decidible.
2. $ l $ no está vacío. Deje que $ m $ sea la longitud mínima de una palabra en $ l $ . Luego, $ l '$ consiste en todas las palabras de longitud al menos $ m $ , y es nuevamente trivialmente decidible (¡En constante tiempo!).

Como puede ver, nunca necesita un algoritmo para $ l $ .

---

De manera similar, el siguiente idioma siempre es decidible:

$$ l ''={w \ in \ sigma ^ * \ mediados \ texto {existe una palabra $ w '\ in l $ de tal que $ | w' | \ geq | w | $}}. $$

Ahora hay tres casos:

1. $ l $ está vacío. En este caso, $ l ''=vacioset $ es trivialmente decidible.
2. $ l $ es infinito. En este caso, $ l ''=sigma ^ * $ es nuevamente triviall decidible.
3. $ l $ es finito. Deje que $ m $ sea la longitud máxima de una palabra en $ l $ . Luego, $ l '' $ consiste en todas las palabras de longitud en la mayoría de $ m $ , y vuelve a ser trivialmente decidible (en tiempo constante).

---

Estos son ejemplos de pruebas no constructivas, que es posible que no le gusten. En lugar de comenzar una discusión aquí, lo remito a esta pregunta .