[Solved]: Are all context-sensitive languages decidable?

ignougroup
Problem Detail: I was going through the Wikipedia definition of context-sensitive language and I found this:

Each category of languages is a proper subset of the category directly above it. Any automaton and any grammar in each category has an equivalent automaton or grammar in the category directly above it.

I could see that linear-bounded automaton is directly below decider in the article’s ordering. If this is the case, then that means every computation on a LBA will halt at some point (since every LBA would be a decider). But I feel that there may be some computation which can run on a LBA at the same time never to halt. For example we can write a computation on LBA which would

  1. read the first symbol on the tape and move right;
  2. read the next symbol and move back left.

This (useless) computation (which is obviously a LB computation) would run indefinitely oscillating left and right and never halt and hence cannot be a decider. Where am I thinking wrong?

Asked By : bongubj

Answered By : A.Schulz

First, all context-sensitive languages are decidable, since they can be accepted by a LBA (as you said), and a Turing machine is more powerful than a LBA. However, you were asking about something else. Can there be LBA that cycles? The answer is yes. You gave an example. However, you can modify every LBA $M$ to a Turing machine $M’$ that accepts the same language but never cycles. To see this, observe, that you can simulate $M$ on $M’$ and keep track of all configurations the LBA has attained so far. If there is one configuration that shows up twice, you detected a cycle. In this case you stop rejecting. The important thing here is that the LBA uses on linear space, and hence the number of its configurations is bounded.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/6108

Leave a Reply