Recursive languages vs context-sensitive languages

In Chomsky's hierarchy, the set of recursive languages is not defined. I know that recursive languages are a subset of recursively enumerable languages and that all recursive languages are decidable.

What I'm curious about is how recursive languages compare to context-sensitive languages. Can I assume that context-sensitive languages are a strict subset of recursive la开发者_运维知识库nguages, and therefore all context-sensitive languages are decidable?

If your question is only if every context sensitive language is in the set of all recursive languages, you should try to prove it the classical way through formal automata. Ask yourself what formal automaton can simulate generation of context sensitive language and what is used to generate recursive language. Then just try to simulate one using the other. Once you look up the right automata in your textbook, you will sure be able to prove what you want.

set of context sensitive languages are a proper subset of recursive languages. You dont have to assume this, refer to Peter Linz's book for proof.

To recognize a recursive language you need a kind of automaton named Decider . It is exactly a Turing Machine tricked by a limited control flow, that is, to ensure it will always halt.

Concerning context-sensitive languages, they are indeed a proper subset of recursive ones. It's trivial giving that the minimal automaton to recognize a context-sensitive language, a Linear bounded automaton is strictly less powerful than a decider. I guess that it would also be possible to demonstrate based on grammar restriction rules.

According to Papadimitriou's book (3.4.2 (e)), context-sensitive grammars are equivalent to NSPACE(n), which is a proper subset of recursive languages. So, yes, your assumption is correct.

As per my references , I would also say that Context Sensitive Languages are a proper subset of a set of all Recursive Languages.You can find this proof in any Standard Textbook like

> An Introduction to Formal Languages and Automata (Edition 5) by Peter Linz