# Decide if a language has a word of a given size

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$$

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.