0
$\begingroup$

I have a question about linear bounded automaton. Is it false that every recursively enumerable language is recognized by a LBA ? Because LBA has limited tape size so not all recursively enumerable languages can be recognized by an LBA because some of them may require unbounded space for their recognition ?

$\endgroup$
1

1 Answer 1

0
$\begingroup$

One answer to your question can be that if all recursively enumerable languages could be recognised by an LBA, Then LBA would be as powerful as Turing machine. Also we know that the set of languages recognisable by a LBA is equal to set of languages produced by context sensitive grammers. Also we know that restricted grammers are more powerful than context sensitive ones. So LBA being as powerful as Turing machine contradicts the fact that there are languages which have restricted grammers but don't have context sensitive ones.

Another answer can be that if LBA is as powerful as Turing machine, Then halting problem for LBA should be unsolvable which is not, So there is some language which can be recognised only by a Turing machine.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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