Linear beschränkte Turingmaschine

Eine linear beschränkte Turingmaschine (auch LBA = Linear Bounded Automaton) in der Theoretischen Informatik ist eine Turingmaschine, die den Bereich des Bandes, auf dem die Eingabe steht, während der gesamten Berechnung nicht verlässt.

Definition

Eine (deterministische) linear beschränkte Turingmaschine ist eine Turingmaschine $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)$ mit folgenden Eigenschaften:

• Das Eingabealphabet $\Sigma$ enthält zwei spezielle Symbole, ein Start- und ein Endsymbol, die das linke und rechte Ende der Eingabe markieren.
• Die Überführungsfunktion überschreibt keinen der Endmarker.
• Wenn das Startsymbol gelesen wird gibt die Überführungsfunktion nicht $L$ aus und wenn das Endsymbol gelesen wird gibt die Überführungsfunktion nicht $R$ aus.

Die obige Definition kann auf Nichtdeterministische Turingmaschine erweitert werden.

Eine nichtdeterministische linear beschränkte Turingmaschine ist eine Nichtdeterministische Turingmaschine $M=(Q,\Sigma ,\Gamma ,\delta ,q_{0},\square ,F)$ mit folgenden Eigenschaften

• Das Eingabealphabet $\Sigma$ enthält zwei spezielle Symbole, ein Start- und ein Endsymbol, die das linke und rechte Ende der Eingabe markieren.
• Die Übergangsrelation überschreibt keinen der Endmarker.
• Wenn das Startsymbol gelesen wird gibt es in der Übergangsrelation kein Übergang mit $L$ und wenn das Endsymbol gelesen wird gibt es in der Übergangsrelation kein Übergang mit $R$.

Alternative Definition

Eine LBA kann ein um einen konstanten Faktor $c$ größeres Band simulieren, indem das Bandalphabet $c$-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 $c$, so dass die Turingmaschine höchstens die ersten $c\cdot n$ Felder des Bandes benutzt, wobei $n$ 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.

Zusammenhang mit kontextsensitiven Sprachen

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

Offene Probleme

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

Literatur

• Uwe Schöning: Theoretische Informatik - kurz gefasst. 5. Auflage. Spektrum Akademischer Verlag, Heidelberg 2008, ISBN 978-3-8274-1824-1, 1.4 Kontextsensitive und Typ 0-Sprachen. 
• Ingo Wegener: Theoretische Informatik. Eine algorithmenorientierte Einführung. B.G. Teubner, Stuttgart, ISBN 3-519-02123-4, 5.4 Kontextsensitive Grammatiken und Sprachen.