Linear Bounded Automata(LBA)

We cannot increase power of Turing Machine by providing some options like 'STAY', '2 Read/Write Head' etc.
But we can restrict power of Turing Machine in following ways:

1. If we use TAPE as STACK then it will be "PDA"
2. If we make TAPE finite then it will be "Finite Automata"
3. If TAPE size is equal to input size then it will be "LBA"

Difference between point 2 and 3
For finite automata TAPE will be of fixed size irrespective of input size, whereas for LBA, TAPE size will varry: for larger input size, larger TAPE and for smaller input size, smaller TAPE size.

---

Power of LBA

LBA is powerful than PDA for example: aⁿbⁿcⁿ | n ≥1
cannot be accepted by PDA whereas it can be accepted by LBA without using any extra space or BLANK symbol.
Approach
Suppose input is : "aaabbbccc"
Mark 'a' as 'X' and move right, mark 'b' as 'X' and move right, mark 'c' as 'X' and move left. And repeat this process till all the symbols are marked equally
For more clarification please go through this link.

---

So till now we have seen all the below machines:

Machine Name	Deterministic and Non-Deterministic Equivalent Status
Finite Automata	Yes
PDA	NO, Non-Deterministic PDA is more powerful
Linear Bounded Automata	Undecidable
Turing Machine	Yes

---

Standard Examples of LBA

Following are standard example of LBA to remember

1. L = {aⁿbⁿcⁿ | n ≥1}
2. L = {a^n! | n ≥ 0}
3. L = {aⁿ | n = m², m ≥ 1}, means n is perfect square
4. L = {aⁿ | n is prime}
5. L = {aⁿ | n is not a prime}
6. L = {ww | w ε {a, b}⁺}
7. L = {wⁿ | w ε {a, b}⁺, n ≥ 1}
8. L = {www^R | w ε {a, b}⁺}