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 Turingmaschinen 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 keinen Übergang mit $L$, und wenn das Endsymbol gelesen wird, gibt es in der Übergangsrelation keinen Ü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 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

Wie auch bei allgemeinen Turingmaschinen kann man die von LBAs akzeptierten Sprachen betrachten. LBAs sind in der Chomsky-Hierarchie, einer Hierarchie von Klassen formaler Grammatiken, von Bedeutung. Die Chomsky-Hierarchie stellt den Zusammenhang zwischen verschiedenen Klassen von Grammatiken und verschiedenen Klassen von Automaten her. Nichtdeterministische LBAs sind dabei die Automatenklasse die den kontextsensitiven Grammatiken entspricht, das heißt die von nichtdeterministischen LBAs akzeptierten Sprachen sind genau die kontextsensitiven Sprachen.

LBA-Probleme

Es gibt zwei bekannte Probleme für linear beschränkte Turingmaschinen, die auf die Arbeit von Kuroda zurückgehen und in der englischsprachigen Literatur oft als „LBA problems“ bezeichnet werden.

Die erste Fragestellung ist, ob jede Sprache, die von einer nichtdeterministischen linear beschränkten Turingmaschine akzeptiert wird, auch durch eine deterministische linear beschränkte Turingmaschine akzeptiert wird, das heißt, ob deterministische und nichtdeterministische LBAs die gleiche Sprachklasse akzeptieren. Diese Fragestellung ist ein offenes Problem der theoretischen Informatik.

Die zweite Fragestellung ist, ob die Sprachklasse die von nichtdeterministischen linear beschränkten Turingmaschinen akzeptiert wird, unter Komplementbildung abgeschlossen ist. Der Satz von Immerman und Szelepcsényi zeigt, dass die Sprachklasse der kontextsensitiven Sprachen (Typ-1) unter Komplementbildung abgeschlossen ist, und löst damit dieses Problem.

Mit Notation aus der Komplexitätstheorie kann die erste Fragestellung als „${\text{NSPACE}}(O(n))={\text{DSPACE}}(O(n))$?“ und die zweite Fragestellung als „${\text{NSPACE}}(O(n))={\text{co-NSPACE}}(O(n))$?“ formuliert werden.

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 1993, ISBN 3-519-02123-4, 5.4 Kontextsensitive Grammatiken und Sprachen.