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)?

Barrada

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.

Hourly

That sure isn't the answer I was hoping for :( though it clarifies a few doubts I had, so thanks! So, if you had to solve the example I wrote at the beginning, how would you proceed (knowing that it's not context-free)? – Barrada

@Jacob- Are you sure it's not context-free? – Hourly

Pretty sure, yeah.. Pumping lemma should rule it out, also I can't find a grammar that would work. – Barrada

@Jacob- Okay, cool. There's no hard-and-fast rule about how to check whether something in in R or RE - R, but remember that R is a very powerful class of languages. Most things involving counting are in R, and a good rule of thumb is that if you can think of a simple computer program to solve it then it's in R. In this case, could you write a program that could check whether the proper string condition held true? – Hourly

Yes, I guess that would be fairly easy.. so you think it would be a good guess to say it's in R, right? – Barrada

@Jacob- Yup. I'd suggest formalizing this by designing a legit TM (or a multitape TM) to prove that you're correct. – Hourly

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

Febrifugal

@ saurabh srivastav what would you say about L={a^n b^m| n,m>=1}, is this CFL? – Clementinaclementine

@aparajitarai I would say, that L is a regular language since, you don't really care about the relationship between the number of a's and the number of b's, you merely say that every string in the language has to start with some non-empty prefix of a's of size n (it is however not defined, what that n should be) followed by a non-empty sequence of b's (where m's upper boundary on length is again not constrained), so you can actually construct a regular expression for this language. Please correct me if I am mistaken. I just taking a course in theoretical computer science at my college. – Goodden