Linear Bounded Automata (LBA) is a single tape Turing Machine with two special tape symbols call them left marker. The transitions should satisfy these conditions: It should not replace the marker symbols by any other symbol. It should not write on cells beyond the marker symbols. A linear bounded automaton (LBA) is an abstract machine that would be identical to a Turing machine, except that during a computation with given input its tape-head is not allowed to move outside a bounded region of its infinite tape, the number of accessible tape-cells being a linear function of the input-size. The tape itself has infinite length in order to accomodate inputs of arbitrary length.

• Automata Theory Tutorial

• Classification of Grammars

• Regular Grammar

• Context-Free Grammars

• Pushdown Automata

• Turing Machine

• Decidability

• Automata Theory Useful Resources

• Selected Reading

A language is called Decidable or Recursive if there is a Turing machine which accepts and halts on every input string w. Every decidable language is Turing-Acceptable.

A decision problem P is decidable if the language L of all yes instances to P is decidable.

For a decidable language, for each input string, the TM halts either at the accept or the reject state as depicted in the following diagram −

Example 1

Find out whether the following problem is decidable or not −

Is a number ‘m’ prime?

Solution

Prime numbers = {2, 3, 5, 7, 11, 13, ………….}

Divide the number ‘m’ by all the numbers between ‘2’ and ‘√m’ starting from ‘2’.

If any of these numbers produce a remainder zero, then it goes to the “Rejected state”, otherwise it goes to the “Accepted state”. So, here the answer could be made by ‘Yes’ or ‘No’.

Hence, it is a decidable problem.

Example 2

Given a regular language L and string w, how can we check if w ∈ L?

Solution

Take the DFA that accepts L and check if w is accepted

Some more decidable problems are −

• Does DFA accept the empty language?
• Is L₁ ∩ L₂ = ∅ for regular sets?

Note −

• If a language L is decidable, then its complement L' is also decidable

• If a language is decidable, then there is an enumerator for it. Download tv serial song honge juda na hum.

• Automata Theory Tutorial

• Classification of Grammars

• Regular Grammar

• Context-Free Grammars

• Pushdown Automata

• Turing Machine

• Decidability

• Automata Theory Useful Resources

• Selected Reading

A linear bounded automaton is a multi-track non-deterministic Turing machine with a tape of some bounded finite length.

Length = function (Length of the initial input string, constant c)

Here,

Memory information ≤ c × Input information

The computation is restricted to the constant bounded area. The input alphabet contains two special symbols which serve as left end markers and right end markers which mean the transitions neither move to the left of the left end marker nor to the right of the right end marker of the tape.

A linear bounded automaton can be defined as an 8-tuple (Q, X, ∑, q₀, ML, MR, δ, F) where −

• Q is a finite set of states

• X is the tape alphabet

• ∑ is the input alphabet

• q₀ is the initial state

• M_L is the left end marker

• M_R is the right end marker where M_R ≠ M_L

• δ is a transition function which maps each pair (state, tape symbol) to (state, tape symbol, Constant ‘c’) where c can be 0 or +1 or -1

• F is the set of final states

A deterministic linear bounded automaton is always context-sensitive and the linear bounded automaton with empty language is undecidable..