views:

75

answers:

1

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 languages, and therefore all context-sensitive languages are decidable?

A: 

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.

Gabriel Ščerbák