1
$\begingroup$

We say that a language $L$ is prefix-free if for every word $s\in L$ there does not exist a nonempty string $w\in\Sigma^*$ such that $sw\in L$ (i.e. no word in the language is a prefix of some other word in the language). For any given language there is a smallest prefix-free sub-language constructed by finding any two words $s,t\in L$ such that $s$ is a prefix of $t$, and removing $t$ from $L$.

Question: Is there a computable language such that its smallest prefix-free sub-language is not computable?

My attempt: I started trying to think of computable languages where "deciding" whether, for any string that is accepted, there exists a longer string which is also accepted, takes infinite time to check. None of the simple examples that come to mind work: If you take for instance any language which accepts finitely many strings, then it and its prefix-free sublanguage are computable. If you take the language of strings that ends in a 1, it and its sublanguage are computable because every string you could accept is a prefix to another accepting string so the sublanguage would be empty.

After trying to come up with simple examples I started thinking maybe I need to work in reverse, and think of a noncomputable language which is the prefix-free sublanguage of a computable language. The obvious language to pick here is the language of machine-input pairs such that the given machine halts on the given input. But I don't see how I could construe this as the prefix-free sublanguage of some other larger computable language. And I've thought a little about a few other noncomputable languages but that hasn't helped at all.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

No, since the change from a language to its smallest prefix-free sub-language is computable.

Suppose language $L$ is computable. That is, we can list all words in $L$ in nondecreasing length. Scanning the list, we will keep only the words that are not an expansion of any word that have been scanned. The list of words left, $P$, is the smallest prefix-free sub-language of $L$. Note that they are also in nondecreasing length. So $P$ is also computable.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I think the answer should be that it is possible. Perhaps I've made a mistake in translation but I am told this related fact: Let $f:\Sigma^*\to \{0,1\}$ be any function and define $Prefree(f)$ to be the function $Prefree(f)(x) = 1$ if and only if $f(x)=1$ and there is no $w\in\Sigma^*$ such that $f(xw)=1$. I am told that there is a computable function $f$ such that $Prefree(f)$ is not computable. I can't come up with an example like that either. I believe this is basically a re-characterization of the same problem but perhaps I'm mistaken. $\endgroup$
    – Addem
    Oct 24, 2021 at 19:38
  • $\begingroup$ @Addem: That problem goes in the other direction - it requires you to determine whether a string is a prefix of any other strings in the language, while determining the smallest prefix-free sub-language of a language only requires determining whether a string has any prefixes in the language. $\endgroup$
    – user2357112
    Oct 25, 2021 at 5:26
  • $\begingroup$ @Addem: That "related fact" is not the same as the problem in your question. Suppose that L contains both s and t, where s is a prefix of t. In your question, the sublanguage would include s but not t; but in that related fact, the sublanguage would include t but not s. This matters because any given string has only finitely many prefixes, but is a prefix of infinitely many other strings; so given t you can certainly check if it has some prefix s in L, but given s you can't necessarily check if it's a prefix of some t in L. $\endgroup$
    – ruakh
    Oct 25, 2021 at 5:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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