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

ignougroup
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