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

What to read next

Please Go through all these linksW3Schools – HTML Tutorial

DefinitionFiber optics is the technology used to transmit information as pulses of light through strands of fiber made of glass or plastic over long