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 exactly the same length as the input.

NOTE: * on the left and # on the right.

Lets consider given Turing machine is M and given string is w,

lets show that the following language is accepted by some LBA:

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

Here, it can be checking by an LBA by the following aspects:

Reject if x is not syntactically correct.

Reject if x doesn't start off in a correct initial configuration.

Reject if any step of the computation trace is incorrect.

Reject if x is a trace showing M rejects w.

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 decide 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.