2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.