LINEAR BOUNDED AUTOMATA (LBA).pptx

Linear bounded automata introduction

1. LINEAR BOUNDED AUTOMATA (LBA) SHAHANA P ROLL NO : 27

2. It behaves as a Turing machine but storage space of tape is restricted only to length of input string. It is 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, ∑, q , ML, MR, δ, F) where − Q is a finite set of states X is the tape alphabet ∑ is the input alphabet q is the initial state M L is the left end marker M R is the right end marker where M R ≠ M L δ is a transition function which maps each pair (state, tape symbol) to (state, tape symbol, Constant ‘c’) where c can be 0 or +1 or -1 F is the set of final states

4. 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.

5. THANK YOU !