Question

Consider these 2 languages:

  • $L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $

  • $L_{<5} = \left \{ \left< M \right> : M \text{ accepts fewer than 5 strings} \right\}$

Are these recursive, R.E., or not R.E. sets (languages)?

I would say that they are not recursive, based on applications of Rice's Theorem.

  • For the first case $L_{e}= \left \{ \left< M \right> :L(M)= \emptyset \right \} \notin L_{\ge5} $ and $L_{\ge5}$ are not empty. For example, I define $L= \left \{ \left< M \right> : M \text{ accepts all palindromes} \right \}$, which is not finite set and accepts an infinite number of strings.

  • For the second case I would do the same thing. I have $L_{e}=\left\{ \left< M \right>: L(M)= \emptyset \right\} \in L_{<5}$ and $L=\left\{ \left< M \right>:M \text{ accepts all palindromes} \right\} \notin L_{<5} $

So I would say that both are not recursive. Is my reasoning correct?

Now about the R.E. of the languages I don't have an idea of how I can prove it, this should be the beginning (if L is not RE it can't be recursive), how can I check if they are RE or not?

From the definition: "$L$ is RE $\iff$ there exists a TM $M$ that accepts $L$", so I just have to define a TM that accepts each language?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top