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:
- If we use TAPE as STACK then it will be "PDA"
- If we make TAPE finite then it will be "Finite Automata"
- If TAPE size is equal to input size then it will be "LBA"
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: anbncn | n ≥1cannot 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- L = {anbncn | n ≥1}
- L = {an! | n ≥ 0}
- L = {an | n = m2, m ≥ 1}, means n is perfect square
- L = {an | n is prime}
- L = {an | n is not a prime}
- L = {ww | w ε {a, b}+}
- L = {wn | w ε {a, b}+, n ≥ 1}
- L = {wwwR | w ε {a, b}+}