Linear Bounded Automata (LBA)
As given below, Linear Bounded Automata (LBA) is a Turing Machine (TM) with a limited-size Input Tape.
LBA = TM + Input Size Tape
Input size Tape: the input size is fixed according to the input. It means if the size of the input is 8 bits, then the size of the input tape will also fix to 8 bits.
Context-sensitive grammar generates context-sensitive languages, which are accepted by Linear 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 Bounded Automata
Some standard examples of Linear Bounded Automata are mentioned below
- L = {anbncn where n≥1}
- L = {an , where n is a prime}
- L = {an , where 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}
