How to determine if a language is recursive or recursively enumerable?

Question

I have to determine whether a language (for example L={a^n b^m c^s | 0<=n<=m<=s}) is regular, context-free, recursive, recursively enumerable or none of them.

I know how to determine if a language is regular (find a DFA or regular expression that works) or context-free (find a PDA or context-free grammar that works); I know that a recursive language has a Turing machine that always halts and that a recursively enumerable language has a Turing machine that may not halt.

So the question is: is there a fast criteria to determine whether the language is recursive or recursively enumerable or neither? For example, I don't have to build a PDA to understand that a language is context-free, I can't see it by the fact that it requires one stack; is there a similar fast approach to the problem (that hopefully saves the trouble to build a Turing machine)?

Answer 1

There's no structural way to check if a language is recursive versus recursively enumerable. There's actually a really cool proof that says that for any automaton capable of recognizing the recursive languages, there's at least one RE language not in R that the automaton also accepts; it's a variant of the diagonalization argument you use to show the existence of undecidable problems.

The main way in which you prove a language is in RE but not R is to prove the language is in RE (perhaps by defining a TM for it), then to reduce a known problem in RE but not R to that problem. For example, if you can show that any instance of the halting problem can be solved by transforming it into an instance of your problem, you know that it can't have a recursive solution, and if you follow this up with a TM for the language you know that the language is in RE. Together, you have a language in RE but not R.

Answer 2

For context free language one quick method is just see the number of comparisions.
In the example see n<=m and m<=s. So there are two comparisons involved. So you can take it out simply telling it is not context free. If there is a single comparison involved then call it as a context free language.

Same is the case with the regular languages. There should be no relation between the two variables, I mean to say there must not be any kind of comparison. For Example consider the languages- 0^m+n 1^n 0^m. Carefully see that there is just a single comparison made which is m+n = n+m(pushing and popping of the symbols) So it is context free.
Now see 0^n+m 1^n+m 0^m clearly see the comparison between the first 2 and the next two.

I took some time to figure it out. But it will take some to make the decisions. Believe me it really works. Here is the last example for regular language. a^n b^2m is regular( See there are no comparisons between n and m) and {a^n b^m |n=2m} is context free as it has only one comparison(not regular)

Hope this helps