in Theory of Computation edited by
1,525 views
0 votes
0 votes
Can anyone give me an example of a language which is not a CSL but can be accepted using a Halting TM?
in Theory of Computation edited by
by
1.5k views

1 comment

Are there any languages that are recursive but not context sensitive?

Yes. But it's complicated thing and it is not even taught in MTech Level Automata Theory Course.

CSL are accepted by LBA(Linear Bounded Automata). LBA are Non deterministic Turing Machines with tape capacity equal to the input string only.
So, LBA are NDTM with limited space (space is Not constant But space available is same as the length of the input string)

So, for any problem to be Recursive But Not CSL, means You can solve the problem by algorithm But you cannot solve the problem using only O(n) space complexity, where n is length of input string.

One popular such language is Set of pairs of equivalent regular expressions.

L = { <R1,R2> | R1,R2 are equivalent regular expressions}

L is Recursive But Not CSL.

https://cs.stackexchange.com/questions/273/decidable-non-context-sensitive-languages

1
1

1 Answer

1 vote
1 vote
It's very rare to find languages which are not csl or not recursive  in today's practical life acc. to wiki "  An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation."

Related questions