linear bounded automaton
A linear bounded automaton, or LBA for short, is a restricted form of a non-deterministic Turing machine with a single tape and a single tape head, such that, given an input word on the tape, the tape head can only scan and rewrite symbols on the cells occupied by the initial input word.
Formally, a linear bounded automaton is a 9-tuple , where
is the state alphabet
is the input alphabet
is the tape alphabet and
are the left and right end markers.
is a function from to , called the next move function
is the start state
is the blank symbol
is the set of final states
The interpretation of is the same as that of a non-deterministic TM: if the is in state and the tape head is reading a tape cell containing , then it replaces by in that tape cell, and move in the direction of ( for left, and for right), and changes its state to . In addition, the next move function has the following properties:
if , then and , and
if , then and .
if and , then .
In other words, if the tape head is reading the left end marker , then if it has a next move, it can only move right without replacing the end marker . Similarly, if it is reading the right end marker , then it can only move left if it has any next move at all, without replacing . Furthermore, no symbol can be replaced by an end marker unless the symbol itself is the end marker.
A configuration of is a triple , where is the current state of , is the content of the tape (including the end markers), and a non-negative integer, the position of the tape head, where is the position of , the left end marker.
Define a binary relation on the set of all configurations of : for ,
where and a non-negative integer, iff any one of the following holds:
Notice that and . If , then the former case can not happen, and if , then the latter case can not happen.
For a given input word , the workspace of an LBA is defined as the portion of the tape between the end markers (including the end markers). In the definition above, we see that , where is the length function. One can enlarge the workspace so that , where are positive integers with and . This is the reason for the name “linear bounded” in LBA. However, the computational power of an LBA with enlarged workspace is not increased: the language accepted by such an LBA can be accepted by an LBA defined above.
A language is context-sensitive iff it can be accepted by an LBA.
It is an open question whether every context-sensitive language can be accepted by a DLBA.
|Title||linear bounded automaton|
|Date of creation||2013-03-22 18:57:40|
|Last modified on||2013-03-22 18:57:40|
|Last modified by||CWoo (3771)|
|Defines||deterministic linear bounded automaton|