A Deterministic Linear Bounded Automaton (LBA) is a single-tape TM that is not a

Question

A Deterministic Linear Bounded Automaton (LBA) is a single-tape TM that is not allowed to move its head past the right end of the input (but it can read and write on the portion of the tape that originally contained the input).

Show the following:

A. It is decidable whether a Deterministic LBA M accepts an input w. Hint: An instantaneous description (ID) of a TM is the current state, the current position of the head, and the current contents of the tape. Give an upper bound on the number distinct ID's to argue how long you need to run the machine before it either halts or must be in an infinite loop.

B. Part A defined a deterministic LBA to make the problem easier. In general, a LBA is defined to be non-deterministic. Generalize your construction for Part A to this case.

Explanation / Answer

LBA, Linear Bound Automation is a multi-tracking Turing Machine (or) multi-track non-deterministic Turing Machine with a tape of some bounded finite length. That is, it has only one tape, and this tape is the same length as the input.

Consider a machine which is a Linear Bounded Automata that has an additional work tape for which the head can move past the right end of the input. The only write operations allowed are the ones that append a non-blank symbol at the end of the non-blank part of the work tape.

If a language A is decidable in polynomial time by an ordinary deterministic Turing Machine, then there is some TM, M and some-time bound which is . It means that M decides the language A in time.

Consider the given Turing machine as M and the given string is w,

Show that the following language A is accepted by some LBA:

L = {x#y L | x is a computation trace of M accepting w and y is any string}

Here, it can be checked by an LBA keeping in mind the following aspects:

·         If x is not syntactically correct, reject it.

·         If x doesn't start off in a correct initial configuration, reject it.

·         If any step of the computation trace is incorrect, reject it.

·         If x is a trace showing that M rejects w, then reject it.

Otherwise accept

Here, this can be possible for a TM to construct a description of the LBA that does this.

If the Turing machine M accepts the string w, then the language is infinite and so the LBA can accept infinitely many inputs. If Turing machine M does not accept string w, then this language is empty. Hence, if a TM can decide whether the LBA had an infinite language, it can be decided whether M accepts w, contradicting that this is impossible.

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.