Linear beschränkter Automat
- 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 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 
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:
Zweikellerautomat — Der Begriff Zweikellerautomat (TPDA) steht in der Theoretischen Informatik für ein besonderes Automatenmodell. Er hat insbesondere für eine einheitliche Darstellung von Automaten Charakterisierungen der Sprachenklassen der Chomsky Hierarchie und… … Deutsch Wikipedia
Auflösbar — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Euklidisch — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Fehlstand — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Integrabel — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Kollinear — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Kopunktal — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Mathematisches Attribut — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Multivariat — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
Primitives Element — In diesem Glossar werden kurze Erklärungen mathematischer Attribute gesammelt. Unter einem Attribut wird eine Eigenschaft verstanden, die einem mathematischen Objekt zugesprochen wird. Ein Attribut hat oft die Form eines Adjektivs (endlich, offen … Deutsch Wikipedia
