0
$\begingroup$

We know that linear bounded automatons accept context-sensitive grammars.

Now suppose that we modify the LBA such that any location of the tape except the input part can be changed.What language does this automaton accept?

I think it is as strong as the standard Turing machine because we can copy the input part somewhere else and work with it like a semi-infinite Turing machine so that its tape is limited from the first symbol of the input that we copied.So it accepts recursively enumerable languages.Is this correct?

| cite | improve this question | |
$\endgroup$
  • 3
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – David Richerby Jun 21 '17 at 21:56
  • $\begingroup$ Well actually when you ask a question and don't mention what you've done for it so far they say this is homework and we don't answer homework questions, so I have to mention my idea about it to show I've worked on it. $\endgroup$ – Winston Jun 21 '17 at 22:02
  • 1
    $\begingroup$ That can sound a bit like a Catch-22, sometimes. But the stuff you have is already essentially a full answer to the question. What do you think might be missing? $\endgroup$ – David Richerby Jun 21 '17 at 22:06
  • $\begingroup$ Well, I believe my answer to this question is too simple to be correct.Actually, I'm not sure about it at all because I'm new to this subject.I don't know maybe I'm thinking in a wrong way. $\endgroup$ – Winston Jun 21 '17 at 22:15
  • $\begingroup$ It looks fine to me. The answers to this kind of question are very often, "You could just simulate a regular Turing machine by [some simple trick]." $\endgroup$ – David Richerby Jun 21 '17 at 22:52
1
$\begingroup$

any location except i/p part means

(total unbounded tape area - tape area that includes i/p string)

= (infinity length - finite length) as we know i/p string length is always finite

= infinity length

in the definition of linear bounded automata it is stated that the tape can be used as a function of the input string length.but here the portion that can be used is of infinite length which is obviously not a function of the input string length.So it acts as a turing machine.

| cite | improve this answer | |
$\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.