12
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Deciding a CSL is independent of whether there are non-terminating LBA: there only has to exist an LBA for it. $\endgroup$ – Raphael Oct 17 '12 at 12:37
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If anyone still did not understand this answer, I suggest you refer to Slide 3-4 of this presentation for additional explanation. $\endgroup$ – bongubj Oct 17 '12 at 6:19
0
$\begingroup$

I suggest you take a look at this book: Introduction to Languages and the Theory of Computation by John E Martin

page 283: There are still open questions concerning context-sensitive languages, such as whether or not every CSL can be accepted by a deterministic LBA.

$\endgroup$
  • $\begingroup$ How does this answer the question? Context-sensitive languages are all decidable, irrespective of whether you need deterministic or nondeterministic linear space. $\endgroup$ – Yuval Filmus Dec 14 '17 at 9:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.