Linear Bounded Automata - LBA

 

 Linear Bounded Automaton (LBA)

A Linear Bounded Automaton (LBA) is basically a Turing Machine whose tape space is restricted — it can only use the portion of the tape that initially contains the input.

In other words:

• The LBA cannot move or write beyond the input boundaries.

• It has two special end markers [ (left) and ] (right) that mark the usable portion of the tape.

• The read–write head “bounces back” if it tries to move beyond these boundaries.

Thus, an LBA is “linear bounded” because the space available to it is linearly proportional to the size of the input.

---

⚙️ Formal Definition 

A Linear Bounded Automaton (LBA) is a nondeterministic Turing Machine

$$M = (Q, \Sigma, \Gamma, \delta, q_0, [ , ], F)$$

with the following properties:

1. Σ (the input alphabet) contains two special symbols [ and ] (the end markers).

2. Γ (the tape alphabet) includes Σ and possibly other symbols for temporary work.

3. The transition function

   $$\delta : Q \times \Gamma \to 2^{Q \times \Gamma \times \{L,R\}}$$
   

   satisfies:

   • For the left end marker [,

     $$\delta(q, [) \subseteq \{(q', [, R)\}$$
     

     i.e., you can read [, but never overwrite or move left of it.

   • For the right end marker ],

     $$\delta(q, ]) \subseteq \{(q', ], L)\}$$
     

     i.e., you can read ], but never overwrite or move right of it.

Thus, the LBA can move around only between the two markers.

---

💡  How an LBA Works

• The input string w is placed between the markers:

  $$[w]$$
  

• The machine starts in state q₀, scanning the leftmost symbol of w.

• It can modify symbols inside the brackets and move left or right—but never cross [ ].

• The machine accepts w if it can enter an accepting state $q_f \in F$ after a finite number of moves.

---

📘 Language Accepted by an LBA

A string $w$ is accepted by an LBA M if there exists some sequence of moves:

$$(q_0, [w]) \vdash^* (q_f, [x_1 x_2])$$

for some $q_f \in F$ and $x_1, x_2 \in \Gamma^*$

That is, starting with input w, the machine halts in an accepting state without leaving the bounded tape area.

The language accepted by M is:

$$L(M) = \{ w \in \Sigma^* \mid M \text{ accepts } w \}$$

---

🧩 Example 1 — $L = \{ a^n b^n c^n \mid n \ge 1 \}$

This is a famous non–context-free language.

• The LBA can mark one a, one b, and one c at a time.

• Each time it marks one triple, it repeats the process.

• Since it never needs space outside the input boundaries, an LBA can accept this language.

Hence,
✅ $L = \{ a^n b^n c^n \mid n \ge 1 \}$is accepted by some LBA,
but ❌ not by any pushdown automaton (PDA).

---

🔍 7. Relationship with Other Machines

Machine Type	Description	Power
Finite Automaton (FA)	No memory (fixed space)	Accepts Regular Languages
Pushdown Automaton (PDA)	One stack (unbounded but linear memory)	Accepts Context-Free Languages
Linear Bounded Automaton (LBA)	Bounded tape (limited memory, proportional to input)	Accepts Context-Sensitive Languages
Turing Machine (TM)	Unbounded tape (unlimited memory)	Accepts Recursively Enumerable Languages

Thus,

$$\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Recursively Enumerable}$$

---

🧭Key Points to Remember

• LBA = Restricted Turing Machine

• The tape is bounded by input length.

• Accepts context-sensitive languages.

• Always nondeterministic in definition

• Has end markers that cannot be crossed or modified.

• Is more powerful than PDA but less powerful than full TM.