Theory of Automata

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}


Help Other’s By Sharing…

Contact Us

Burewala, Vehari, Punjab, Pakistan


Pin It on Pinterest