Linear beschränkte Turingmaschine

Turingmaschine, die nur den Speicher der Eingabe verwendet
(Weitergeleitet von Linear beschränkter Automat)

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

Bearbeiten

Eine (deterministische) linear beschränkte Turingmaschine ist eine Turingmaschine   mit folgenden Eigenschaften:

  • Das Eingabealphabet   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   aus, und wenn das Endsymbol gelesen wird, gibt die Überführungsfunktion nicht   aus.

Die obige Definition kann auf nichtdeterministische Turingmaschinen erweitert werden.

Eine nichtdeterministische linear beschränkte Turingmaschine ist eine Nichtdeterministische Turingmaschine   mit folgenden Eigenschaften

  • Das Eingabealphabet   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  , und wenn das Endsymbol gelesen wird, gibt es in der Übergangsrelation keinen Übergang mit  .

Alternative Definition

Bearbeiten

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

Bearbeiten

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

Bearbeiten

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.[1]

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 „ ?“ und die zweite Fragestellung als „ ?“ formuliert werden.

Literatur

Bearbeiten
  • 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.

Einzelnachweise

Bearbeiten
  1. Sige-Yuki Kuroda: Classes of languages and linear-bounded automata. In: Information and Control. Band 7, Nr. 2, Juni 1964, S. 207—223, doi:10.1016/s0019-9958(64)90120-2 (sciencedirect.com [PDF]).