Whats the difference between context sensitive language and recursive language?
Answers
Answered by
0
Answer:
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.
Answered by
4
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
Similar questions