Menu
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?
753
Context sensitive languages are closed under union, intersection, complement, concatenation, kleene star, reversal. Every Context sensitive language is recursive.
The main difference is that in recursively enumerable language the machine halts for input strings which are in language L. but for input strings which are not in L, it may halt or may not halt. When we come to recursive language it always halt whether it is accepted by the machine or not.
A Context Sensitive Language is one that may be described by a Context Sensitive Grammar, according to formal language theory and equivalently by a noncontracting grammar. One of the four categories of grammar in the Chomsky hierarchy is context-sensitive.
A language is recursively enumerable (r.e.) if it is the set of strings accepted by some TM. A language is recursive if it is the set of strings accepted by some TM that halts on every input. For example, any regular language is recursive.
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.
82
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.
37
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
