LBA 1213412512365jytdjtdjgtdjgfdjgfjgjgj

bnfxhbnxfhbn

1. LINEAR BOUNDED
AUTOMATA (LBA)

SHAHANA P
ROLL NO : 27

2. = |t behaves as a Turing machine but storage space of tape is restricted only to length of input string.

® Itis less powerful than TM and more powerful than PDA.

= The computation is restricted to the constant bounded area.

= The input alphabet contain two special symbols which serve as left end marker and right end marker
which means the transition neither move to left of the left end marker nor to right of the right end marker,

. Linear bounded automata accepts context sensitive language.

3. A linear bounded automaton can be defined as an 8-tuple (Q, X, E, qq, ML, MR, 8, F) where -
*Qis a finite set of states

+X is the tape alphabet

*E is the input alphabet

“a is the initial state

“M, is the left end marker

“Mais the right end marker where My # M,

+6 is a transition function which maps each pair (state, tape symbol) to (state, tape symbol, Constant ‘e’) where ¢
can be 0 or +1 or-1

*Fis the set of final states

4. LINEAR BOUNDED AUTOMATA

r Mi Ma A

LEFT ENDED RIGHT ENDED
MARKER MARKER

Working Space

5. LBA - APPLICATIONS
* For implementation of genetic programming

= For constructing syntactic parse tree for semantic analysis for the compiler

EXPRESSIVE POWER OF VARIOUS AUTOMATA

Expressive power can be determined from the class or set of languages accepted by that particular type
of machine. Here is the increasing sequence of expressive power of machines.

FA < DPDA < PDA < LBA < TM

6. THANK YOU !