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 M=(Q,Σ,Γ,δ,q0,B,F,\Yleft,\Yright), where

  1. 1.

    Q is the state alphabet

  2. 2.

    Σ is the input alphabet

  3. 3.

    Γ is the tape alphabet and ΣΓ

  4. 4.

    \Yleft,\YrightΣ are the left and right end markers.

  5. 5.

    δ is a function from Q×Γ to P(Q×Γ×{L,R}), called the next move function

  6. 6.

    q0Q is the start state

  7. 7.

    BΓ-Σ is the blank symbol

  8. 8.

    FQ is the set of final states

The interpretationMathworldPlanetmathPlanetmath of (q,b,D)δ(p,a) is the same as that of a non-deterministic TM: if the M is in state p and the tape head is reading a tape cell containing a, then it replaces a by b in that tape cell, and move in the direction of D (D=L for left, and D=R for right), and changes its state to q. In additionPlanetmathPlanetmath, the next move function δ has the following properties:

  • if (q,b,D)δ(p,\Yleft), then b=\Yleft and D=R, and

  • if (q,b,D)δ(p,\Yright), then b=\Yright and D=L.

  • if (q,b,D)δ(p,a) and a{\Yleft,\Yright}, then b{\Yleft,\Yright}.

In other words, if the tape head is reading the left end marker \Yleft, then if it has a next move, it can only move right without replacing the end marker \Yleft. Similarly, if it is reading the right end marker \Yright, then it can only move left if it has any next move at all, without replacing \Yright. Furthermore, no symbol can be replaced by an end marker unless the symbol itself is the end marker.

An LBA is also known as a non-deterministic LBA, or NLBA for short. An LBA is said to be deterministicMathworldPlanetmath (abbreviated as DLBA) if δ(p,a) is at most a singleton for every pair (p,a)Q×Γ.

A configuration of M is a triple (p,u,i), where pQ is the current state of M, u{\Yleft}Γ*{\Yright} is the content of the tape (including the end markers), and i a non-negative integer, the position of the tape head, where i=0 is the position of \Yleft, the left end marker.

Define a binary relationMathworldPlanetmath on the set of all configurations of M: for ai,bΓ,

(p,a0ai-1aai+1an+1,i)(q,a0ai-1bai+1an+1,j),

where i=1,,n and n a non-negative integer, iff any one of the following holds:

(q,b,L)δ(p,ai) and j=i-1  or  (q,b,R)δ(p,ai) and j=i+1.

Notice that a0=\Yleft and an+1=\Yright. If i=0, then the former case can not happen, and if i=n+1, then the latter case can not happen.

Take the reflexive transitive closure * of , and set

L(M):={uΣ*(q0,\Yleftu\Yright,0)*(q,\Yleftv\Yright,j) for some qF}

the languagePlanetmathPlanetmath accepted by M.

Remarks

  • For a given input word u, the workspace w(u) 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 |w(u)|=|u|+2, where || is the length function. One can enlarge the workspace so that |w(u)|=r|u|+s, where r,s are positive integers with r1 and s2. 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.

  • Every context-free language can be accepted by a DLBA, but not conversely.

  • It is an open question whether every context-sensitive language can be accepted by a DLBA.

References

Title linear bounded automaton
Canonical name LinearBoundedAutomaton
Date of creation 2013-03-22 18:57:40
Last modified on 2013-03-22 18:57:40
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 10
Author CWoo (3771)
Entry type Definition
Classification msc 68Q45
Synonym LBA
Synonym NLBA
Synonym DLBA
Synonym deterministic LBA
Related topic ContextSensitiveGrammar
Related topic ContextSensitiveLanguage
Defines deterministic linear bounded automaton