Linear bounded automaton

Linear bounded automaton

A linear bounded automaton (plural linear bounded automata, abbreviated LBA) is a restricted form of a non-deterministic Turing machine. It possesses a tape made up of cells that can contain symbols from a finite alphabet, a head that can read from or write to one cell on the tape at a time and can be moved, and a finite number of states. 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. This limitation makes an LBA a more accurate model of computers that actually exist than a Turing machine in some respects.

Linear bounded automata are acceptors for the class of context-sensitive languages. The only restriction placed on grammars for such languages is that no production maps a string to a shorter string. Thus no derivation of a string in a context-sensitive language can contain a sentential form longer than the string itself. Since there is a one-to-one correspondence between linear-bounded automata and such grammars, no more tape than that occupied by the original string is necessary for the string to be recognized by the automaton.

External links

* [http://www.cs.uky.edu/~lewis/texts/theory/automata/lb-auto.pdf Linear Bounded Automata] by [http://www.cs.uky.edu/~lewis/ Forbes D. Lewis]
* [http://www.cs.uiowa.edu/~fleck/PartIIIxpar/sld006.htm Linear Bounded Automata] slides, part of [http://www.cs.uiowa.edu/~fleck/PartIIIxpar/ Context-sensitive Languages] by [http://www.cs.uiowa.edu/~fleck Arthur C. Fleck]
* [http://www.seas.upenn.edu/~cit596/notes/dave/chomsky2.html Linear-Bounded Automata] , part of Theory of Computation syllabus, by David Matuszek


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Linear Bounded Automaton — Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA …   Deutsch Wikipedia

  • Linear beschränkte Turing-Maschine — Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA …   Deutsch Wikipedia

  • Linear beschränkte Turingmaschine — Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA …   Deutsch Wikipedia

  • Linear beschränkter Automat — Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) ist eine Turingmaschine, die den Eingabebereich nicht verlässt. Das bedeutet, dass sie nur den Teil des Bandes benutzt, auf dem zu Beginn das Eingabewort steht. Eine LBA …   Deutsch Wikipedia

  • Lazy linear hybrid automaton — Lazy linear hybrid automata model the discrete time behavior of control systems containing finite precision sensors and actuators interacting with their environment under bounded inertial delays. The model permits only linear flow constraints but …   Wikipedia

  • Pushdown automaton — In automata theory, a pushdown automaton (PDA) is a finite automaton that can make use of a stack containing data. Operation Pushdown automata differ from normal finite state machines in two ways: # They can use the top of the stack to decide… …   Wikipedia

  • Deterministic pushdown automaton — In automata theory, a pushdown automaton is a finite automaton with an additional stack of symbols; its transitions can take the top symbol on the stack and depend on its value, and they can add new top symbols to the stack. A deterministic… …   Wikipedia

  • Nested stack automaton — In automata theory, a nested stack automaton is a finite automaton that can make use of a stack containing data which can be additional stacks.[1] A nested stack automaton may read its stack, in addition to pushing or popping it. A nested stack… …   Wikipedia

  • Deterministic automaton — is a concept of automata theory in which the outcome of a transition from one state to another given a certain input can be predicted for every occurrence. A common deterministic automaton is a deterministic finite state machine (sometimes… …   Wikipedia

  • automata theory — Body of physical and logical principles underlying the operation of any electromechanical device (an automaton) that converts information input in one form into another, or into some action, according to an algorithm. Norbert Wiener and Alan M.… …   Universalium

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”