0
$\begingroup$

I am trying to prove the following:

Let $\Sigma $ be an alphabet not containing the symbol "$;$", and suppose that $L \subseteq \Sigma^*$; $\Sigma^*$ is recursively enumerable. If this is the case language $L' = \{x \in \Sigma^*: x; y \in L \ for \ some \ y \in \Sigma^*\}$ is recursively enumerable.

which left me a little bit confused. Since $";"$ is not in the alphabet $\Sigma$ should I seperate $x$ and $y$ and show that check for $x \in \Sigma^*$ and $y \in \Sigma^*$ is recursively enumerable?

Also, will this statement be the case if we checked for being recursive instead, that is if $L$ was recursive, is $L'$ necessarily recursive as well? And is the proof of this the same with the recursively enumerable case?

Any help will be appreciated.

$\endgroup$
1
$\begingroup$

First, a few things that may or may not help:

  • Def: A language $L\subseteq \Sigma ^*$ is Recursive (R) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$ and $0$ iff $u\not\in L$.

  • Def: A language $L\subseteq \Sigma ^*$ is Recursively enumerable (RE) if there is some algorithm that, when given $u\in \Sigma^*$, will return $1$ iff $u\in L$. (If $u\not\in L$, ir may return $0$ or loop forever)

  • Prop: A language $L$ is RE iff there is some algorithm that enumerates $L$. One way to formalize "$\mathcal A$ enumerates $L$" would be to say that the algorithm $\mathcal A$ takes an integer $n\in \mathbb N$ and returns some $\mathcal A(n)\in L$ for each $n$, and that for any $u\in L$ there is at least one $n$ so that $\mathcal A(n)=u$ (i.e. if you look at the algorithm as a function $\mathcal A:\mathbb N \to L$, it is surjective).

  • Remark: Even though the notins of R and RE seem to depend on the alphabet, they do not. If you have an algorithm $\mathcal A$ that takes a word $u\in \Sigma$ as input, you create the one that takes $u\in \Sigma'^*$ by returning $0$ if $u\not\in \Sigma$ (which is decidable) and then running $\mathcal A$. And in the other direction, you can just reuse the same algorithm.


Now, take some alphabet $\Sigma$ so that $;\not\in\Sigma$ and let $\Sigma':=\Sigma\sqcup \{;\}$.

To show that your $L'$ is indeed RE, just take the algorithm $\mathcal A$ that proves that $L$ is RE. When given $x\in \Sigma^*$, you want to know if there is some $y\in \Sigma^*$ so that $x;y\in L$. The problem with simply trying for each $y\in \Sigma^*$ is that your first call to $\mathcal A$ may never terminate and you'll have looped on a possibly positive instance. What you want to do instead is this: for $n$ from $0$ to $+\infty $, for each word $y\in \Sigma^*$ of size $|y|\le n$, run $\mathcal A$ on $y$ for $n$ steps (or seconds) and if it returns $1$, return $1$. So you're trying bigger a bigger $y$ while giving more and more time to $\mathcal A$ to finish. If there is some $y$ so that $x;y\in L$, then you'll eventually try for this $y$ and give $\mathcal A$ enough time to tell you it's the corect $y$. And if it answers yes, then clearly, there is some $y$ so that $x;y\in L$. So we just proved that $L'$ is RE.

Using the property I gave above, there is another simpler proof. You suppose that you can enumerate $L$ and want to enumerate $L'$. Well clearly, you just have to enumerate $L'$ and drop the $;$ and whatever is after it.

If you suppose that $L$ is R then $L'$ may not be R. Recall that the halting problem $HALT=\{\langle M,w\rangle|M\text{ halts on input }w\}$ is undecidable (i.e. $HALT\not\in R$). Let $BHALT:=\{\langle M,w\rangle;n|M\text{ halts on input }w\text{ in at most }n\text{ steps}\}$. Clearly $BHALT\in R$: you can just simulate $M$ on $w$ for $n$ steps and then check if the last state is final. But if you take $L=BHALT\in R$, then $L'=HALT\not \in R$.

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