Linear beschränkte Turingmaschine

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 kann ein um einen konstanten Faktor n größeres Band simulieren, indem das Bandalphabet n-Tupel des Eingabealphabetes enthält. Entsprechend wäre auch eine Definition denkbar, bei der gleich ein um einen konstanten Faktor größeres Band vorgesehen wird. Das heißt, es gibt eine konstante Zahl n, so dass die Turingmaschine höchstens die ersten n \cdot x Felder des Bandes benutzt, wobei x die Länge des Eingabewortes ist. Die nutzbare Bandlänge ist dann also linear in der Länge der Eingabe. Dies erklärt das "Linear" im Namen der LBA.

Die von nichtdeterministischen LBAs akzeptierten Sprachen sind genau die kontextsensitiven Sprachen (vgl. Chomsky-Hierarchie).

Es ist ein offenes Problem, ob deterministische LBAs die gleiche Sprachklasse akzeptieren wie die nichtdeterministischen.


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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 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ä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

  • Nichtdeterministische Turingmaschine — Eine nichtdeterministische Turingmaschine (NTM, NDTM) in der Theoretischen Informatik ist eine Turingmaschine, die anstatt einer Übergangsfunktion eine Übergangsrelation verwendet. Inhaltsverzeichnis 1 Informelle Beschreibung 2 Formale Definition …   Deutsch Wikipedia

  • Chomsky-Typ — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Chomsky Hierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Chomskyhierarchie — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Kontext-sensitive Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-0-Grammatik — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

  • Typ-0-Sprache — Chomsky Hierarchie, gelegentlich Chomsky–Schützenberger Hierarchie, (benannt nach dem Linguisten Noam Chomsky und dem Mathematiker Marcel Schützenberger) ist ein Begriff aus der Theoretischen Informatik und bezeichnet eine Hierarchie von Klassen… …   Deutsch Wikipedia

Share the article and excerpts

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