Decide if a language has a word of a given size

Question

Suppose that $L$ is some language over the alphabet $\Sigma$. I was asked to show that the following languages is decidable:

$$L' = \{w \in \Sigma^* | \text{ there exists a word } w'\in L \text{ such that } |w'| \leq |w| \}$$

I.e., $w \in L'$ if $L$ has some word with length smaller than $|w|$.

The way I was thinking to show that is observing that $L \cap\Sigma^{|w|}$ is finite, and $(L \cap \Sigma) \cup (L \cap \Sigma^2) \cup \ldots\cup (L\cap \Sigma^{|w|})$ is finite too, hence decidable. But the main thing I am struggling with is how can any algorithm for $L'$ know if some $u \in L$? this is undecidable, so it's unclear to me how any algorithm for $L'$ can verify that indeed some word is in $L$

Answer 1

There are two cases:

1. $L$ is empty. In this case, $L' = \emptyset$ is trivially decidable.
2. $L$ is non-empty. Let $m$ be the minimum length of a word in $L$. Then $L'$ consists of all words of length at least $m$, and is again trivially decidable (in constant time!).

As you can see, you never actually need an algorithm for $L$.

---

Similarly, the following language is always decidable:

$$L'' = \{w \in \Sigma^* \mid \text{ there exists a word $w' \in L$ such that $|w'| \geq |w|$}\}.$$

There are now three cases:

1. $L$ is empty. In this case, $L'' = \emptyset$ is trivially decidable.
2. $L$ is infinite. In this case, $L'' = \Sigma^*$ is again triviall decidable.
3. $L$ is finite. Let $M$ be the maximum length of a word in $L$. Then $L''$ consists of all words of length at most $M$, and is again trivially decidable (in constant time).

---

These are examples of non-constructive proofs, which you might not like. Instead of starting a discussion here, I refer you to this question.