I am currently under the believe that all regular languages are context free, thus all regular languages are recursive, and therefore all regular languages are recursively enumerable.

If I am given a question where one must select exactly one of these types of a languages for a given language L, then for each language the answer must be recursively enumerable? Am I correct in this assumption or am I missing something? Point me in the right direction if so.

  • 1
    $\begingroup$ Usually you’re expected to respond with the most restrictive classification that applies. Thus, if the language is regular, you should pick regular. If it’s context-free but not regular, you should pick context-free. And so on. $\endgroup$ – Brian M. Scott Nov 29 '12 at 19:56
  • $\begingroup$ Ok that is probably what I am supposed to do, thanks. $\endgroup$ – Matt Nov 29 '12 at 20:00
  • $\begingroup$ You’re welcome. $\endgroup$ – Brian M. Scott Nov 29 '12 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.