![]() ![]() A pertinent difference between an LBA and a FSA is that the number of states of an FSA is fixed for that FSA, while the number of states of an LBA varies as a linear function of the amount of input given to that LBA. Unlike a Turing machine system, an LBA system (the finite state machine plus its tape) has only finitely many system states for each input that is, for each input, an LBA system behaves as a finite automaton. Like the Turing machine, an LBA is a finite state machine equipped with a tape. In this alternative version, there is a supply of infinitely many finite tapes, there being one tape for each input-size.) (An equivalent alternative version of this model supplies the LBA with a different finite-length tape for each input of different size, the length of the tape being a linear function of the input-size. The tape itself has infinite length in order to accomodate inputs of arbitrary length. A linear bounded automaton (LBA) is an abstract machine that would be identical to a Turing machine, except that during a computation with given input its tape-head is not allowed to move outside a bounded region of its infinite tape, the number of accessible tape-cells being a linear function of the input-size. ![]()
0 Comments
Leave a Reply. |
Details
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |