9/16/2023 0 Comments Linear bounded automaton![]() Since the size of the accessible tape is bounded by some linear function of the length of the input, the linear bounded automaton is computationally equivalent to a nondeterministic Turing machine restricted to the portion of the tape containing the input, hence the name linear bounded automaton. ![]() Instead of having potentially infinite tape on which to compute, computation is restricted to the portion of the tape containing the input plus the two tape squares holding the endmarkers. It differs from a Turing machine in that while the tape is initially considered to have unbounded length, only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |