# R.E or non R.E?

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

• 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?
– Raphael
Jan 9 '18 at 16:52
• 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!
– Raphael
Jan 9 '18 at 16:52

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.
• 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 ? Jan 9 '18 at 16:53
• @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$. Jan 9 '18 at 17:46