0
$\begingroup$

Can anyone give an example where a language can be rejected by linear bounded automata and accepted by a Turing machine. Is there any proof that a linear bounded automata is less powerful than a Turing machine?

$\endgroup$
  • $\begingroup$ Does this answer your question? Are Linear Bounded Automatons Turing Complete? $\endgroup$ – ttnick Jun 29 at 15:23
  • $\begingroup$ @ttnick it answers partially $\endgroup$ – Vamsi Shankar Jun 29 at 16:56
  • $\begingroup$ @ttnick can i say that one of the difference is there will be no epsilon on the LHS side of productions of LBA but in a turing machine, epsilon productions can exist on the LHS side? $\endgroup$ – Vamsi Shankar Jun 29 at 17:01
1
$\begingroup$

Notice that linear bounded automata are precisely all TM's who use $O(n)$ space.

Now, by the space-hierarchy theorem, for any $f$ where $n=o(f)$ (for an extreme example, $f(n)=2^n$) we would have $DSPACE(O(n))\subsetneq DSPACE(O(f))$.

Thus there are languages who require space complexity bigger than $O(n)$, and therefore are not solveable by linear bounded automata but can be solved by a ($O(f)$ space) turing machine.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you give any example of such language which is rejected by LBA but accepted by a Turing machine? $\endgroup$ – Vamsi Shankar Jun 29 at 16:58
  • $\begingroup$ Can i say that one of the difference is there will be no epsilon on the LHS side of productions of LBA but in a turing machine, epsilon productions can exist on the LHS side? $\endgroup$ – Vamsi Shankar Jun 29 at 17:02
  • $\begingroup$ What do you mean by epsilon productions? $\endgroup$ – nir shahar Jun 29 at 17:39
  • $\begingroup$ And for an example, take a look at the proof: It builds a language in $O(f)$ that is not in $O(g)$, for $g=o(f)$. In our case, $g(n)=n$. $\endgroup$ – nir shahar Jun 29 at 17:43

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.