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}+}

Contributor's Info

Introduction To PushDown Automata

In order to accept Context free language we need a machine which is similer to finit automata. It is nothing but a finit automata to which a memory is added i.e stack.

                   FA + Stack=PDA


Q : Finite Set of states

∑ : Input symbol

δ  : Transition Function

q0 : Initial Symbol

Z: Bottom of the stack

F  :  Set of final states

X  : Stack alphabet( means what are the symbol that we allow to be present on to the top of the statck)

 PDA is of two type:

1. Deteministic PDA:


δ  : Q x {∑ ∪ ∈} x X     ---->   Q x X*



2. Non Detesministic PDA:


δ  : Q x {∑ ∪ ∈} x X      ---->    2Q x X*



Contributor's Info

Theory of Computation | What are the fundamental capabilities and limitations of computers?
In theoretical computer science and mathematics, the theory of computation is the branch that deals with how efficiently problems can be solved on a model of computation, using an algorithm. The field is divided into three major branches: automata theory and languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?”

Contributor's Info

Created: Edited:
Rajesh @rajeshrajput1 9 Feb 2019 01:54 pm
very good experence