2
$\begingroup$

During a lesson, our TA asked:

What kind of languages can be recognized by a deterministic Turing Machine such that we can use only a tape portion that contains the input?

My thoughts: my Theory of Computation book says that there is a special TM called linear bounded automaton (LBA) that corresponds to a non-deterministic Turing Machine that has a limited tape. Such machine recognize Context Sensitive languages.

So if i simulate the LBA behavior starting from a deterministc TM, may I recognize "deterministic"-Context Sensitive Languages?

$\endgroup$
2
$\begingroup$

It's famously unknown whether deterministic and non-deterministic LBA accept the same set of languages.

$\endgroup$

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.