Linear Bound Automata (LBA)
Linear Bound Automata (LBA) is Turing Machine (TM) with limited size Input Tape as given below
LBA = TM + Input Size Tape
Input size Tape: the size of input is fixed according to given input. It means if the size of input is 8-bits then size of input tape will also fix to 8-bits.
Context sensitive grammar generates context sensitive languages which are accepted by Linear bound Automata machines.
Note: LBA are more power full than PDA but less power full than Turing Machine. So LBA accept all regular and context free languages but cannot accept the recursive languages.
Standard Examples of Linear Bound Automata
Some standard examples of Linear Bound Automata are mentioned below
- L = {anbncn where n≥1}
- L = {an where n is a prime}
- L = {an where n is non prime}
- L = {an! where n≥a}
- L = {ww where w∈ (a,b)+}
- L = {wwwR where w∈ (a,b)+}
- L = {wn where w∈ (a,b)+ n≥1}
- L = {an where n= m2, m≥1}