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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
0

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.