Linear Bounded Automata(LBA)

We can't increase the power of turing machine by giving them more tape and facility. If we limit the tap to be used as stack and non determiniam then it will ac t as a push down automata, Now come to linear bounded automata ,LBA is a TM which restricted ,means it is not suppose to use beyond the input.
LBA= TM +Tape(input)
Note: 1)This LBA is less powerful than TM. '
eg. anbncn
not accepted by PDA, but this language can be accepted by LBA accordingly. So LBA is powerful than PDA
2)Whenever we talking about power ,we are talking about taking them as non deterministic machine in all the cases.[i.e FA,PDA,LBA,TM ]

 

These are example which are accepted by LBA.

1) L ={anbncn  ,n>=1}

 

2) L={an!  ,n>=0}

 

3) L={a ,n=m2  ,m>=1}

 

4)L={an  ,n is a prime}

 

5) L={an  ,n is not a prime}

 

6) L={ww   ,w∈ {a,b}+ }

 

7) L={wn   ,w∈ {a,b}+ ,n>=1}

 

8)L={wwwr  ,w∈ {a,b}+}

0Comment