1
$\begingroup$

$L_1= \{ \langle M \rangle \mid L(M) \text{ is strings of length between } 1 \text{ and } 5 \}$.

$L_2 = \{ \langle M \rangle \mid L(M) \text{ is strings of length at most } 5\}$.

I am able to figure out that both languages are undecidable as we can have $TM_{yes}$ and $TM_{no}$ and as per Rice's theorem it's undecidable . But I am having difficulty in proving whether the language is R.E or non R.E .

Can someone please help me?

|cite|improve this question
$\endgroup$
  • $\begingroup$ What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael♦ Jan 9 '18 at 16:52
  • $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael♦ Jan 9 '18 at 16:52
1
$\begingroup$

Hint: both $\overline{L}_1$ and $\overline{L}_2$ are recursively enumerable. For example, to show that $\overline{L}_1$ is r.e., given $\langle M \rangle$ use dovetailing until you find a string $w$ accepted by $M$ and having length $0$ or greater than $5$. If such string is found, then accept $\langle M \rangle$. This means that if both $L_1$ and $L_2$ are not recursive (as you claim) then $L_1$ and $L_2$ cannot be r.e., since this would imply that $L_1$ and $L_2$ are recursive.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ For L1, we have finite number of strings of length between 1 and 5 so we can simulate all these strings on each TM in an interleaved manner (dovetailing) and hence it's R.E right ? For L2, $TM_{yes} = \phi$ and $TM_{no}$ = any string of length greater than 5. As $TM_{yes}$ is subset of $TM_{no}$ , it should be non r.e right ? $\endgroup$ – Rajesh R Jan 9 '18 at 16:53
  • $\begingroup$ My main doubt is why can't we apply the same logic to L2 ? We have finite amount of strings of length atmost 5 right ? It should also be R.E by dovetailing. But by Rice's theorem it's non r.e as I mentioned in my previous comment. $\endgroup$ – Rajesh R Jan 9 '18 at 17:17
  • $\begingroup$ If we apply the same logic to L2 then it should be R.E but it's non R.E by rice theorem . $\endgroup$ – Rajesh R Jan 9 '18 at 17:25
  • 1
    $\begingroup$ @RajeshR Even if you feed all strings of length between $1$ and $5$ to $M$ and observe that $M$ halts on all of them, that does not guarantee that $M$ does not accept another string $w$ of length greater than $5$. The number of strings is infinite. You cannot check all of them in a finite number of steps. So, dovetailing does not guarantee that $L_1$ is r.e. Similarly for $L_2$. $\endgroup$ – fade2black Jan 9 '18 at 17:46
  • $\begingroup$ Ok. Got it now. $\endgroup$ – Rajesh R Jan 9 '18 at 17:51

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.