Linear Bounded Automata PDF

Preview

Summary

This is easy to learn lecture note for linear bounded automata....

Description

Linear Bounded Automata (LBA) It is a variant of turing machine (TM), which is created by restricting the way in which the tape can be used.  It has an unbound tape similar to the case of standard TM.  The tape head is not allowed to move off the portion of the tape containing the input.  The input is restricted using some special symbols, namely the left end marker ([) and right end marker (]).  More space is available for long input strings and less space for short input strings.  The initial configuration is given b y the instantaneous description q0, where q0 is the initial state, is the input string, ‘[‘is the left end marker, and ‘]’ is the right end marker.  LBA is a TM with a limited amount of memory; it can solve only problems requiring memory that can fit within the tape used for the input.  LBA accepts context sensitive language.  In spite of memory constraints, LBA’s are powerful....