[Solved]: Show that a language is RE or recursive

Problem Detail: 

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?

Asked By : newbie

Answered By : jmite

$L_{\geq5}$ is RE. Basically, given a machine $M$, you iterate through all strings, starting with all of length 0, then length 1, etc. You simulate $M$ and test if the current string $s$ is accepted by $M$. If it is, then you increment some counter. If the counter ever hits 5, you accept. There's no guarantee that this will terminate, which is why it's RE and not recursive. There is a guarantee, however, that it will terminate for any input machine $M$ that does accept 5 or more strings.

We know from Rice's theorem that $L_{\geq5}$ is not recursive, and since it is RE, then we know its compliment is not RE. So $L_{<5}$ is neither RE or recursive.

Intuitively, you could iterate through all strings, but there would never be a point where you could say "Based on the strings I've seen so far, I know that this machine accepts less than 5 strings." Even if you accept less than 5 so far, there's no way of knowing that there aren't larger strings which would be accepted.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/17889

 Ask a Question

 Download Related Notes/Documents