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

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 ? – Rajesh R 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$. – fade2black Jan 9 '18 at 17:46