Linear beschränkte Turingmaschine

Grundidee und Bedeutung

Eine linear beschränkte Turingmaschine, kurz LBA (Linear Bounded Automaton), ist ein Rechenmodell der Theoretischen Informatik. Sie arbeitet auf einem Band, darf während der gesamten Berechnung jedoch nur den Bereich benutzen, auf dem die Eingabe steht. Dadurch hängt der verfügbare Speicher höchstens linear von der Länge der Eingabe ab. LBAs sind deshalb besonders wichtig, wenn untersucht wird, welche formalen Sprachen mit begrenztem Speicher akzeptiert werden können.

Man betrachtet sowohl deterministische als auch nichtdeterministische LBAs. Bei einer deterministischen Maschine ist der nächste Rechenschritt durch den aktuellen Zustand und das gelesene Bandsymbol eindeutig festgelegt. Bei einer nichtdeterministischen Maschine kann es mehrere mögliche Übergänge geben; eine Eingabe wird akzeptiert, wenn mindestens einer der möglichen Berechnungswege akzeptiert.

Definition der LBA

Eine deterministische linear beschränkte Turingmaschine ist eine Turingmaschine M=(Q,Σ,Γ,δ,q₀,□,F) mit besonderen Einschränkungen:

• Das Eingabealphabet Σ enthält zwei spezielle Symbole: ein Startsymbol und ein Endsymbol. Sie markieren das linke beziehungsweise rechte Ende der Eingabe.
• Die Überführungsfunktion überschreibt keinen der beiden Endmarker.
• Wird das Startsymbol gelesen, gibt die Überführungsfunktion nicht L aus. Die Maschine darf sich also dort nicht nach links bewegen.
• Wird das Endsymbol gelesen, gibt die Überführungsfunktion nicht R aus. Die Maschine darf sich dort nicht nach rechts bewegen.

Damit bleibt der Kopf der Turingmaschine während der gesamten Berechnung zwischen den beiden Endmarkierungen. Die Definition lässt sich auf nichtdeterministische Turingmaschinen erweitern. In diesem Fall wird die Überführungsfunktion durch eine Übergangsrelation ersetzt. Auch dann werden die Endmarker nicht überschrieben. Beim Lesen des Startsymbols gibt es keinen Übergang mit L, beim Lesen des Endsymbols keinen Übergang mit R.

Alternative Begrenzung des Bandes

Eine LBA kann ein um einen konstanten Faktor c größeres Band simulieren, wenn ihr Bandalphabet c-Tupel des Eingabealphabets enthält. Deshalb kann man die Definition auch so formulieren, dass die Maschine nicht nur genau den Eingabebereich, sondern höchstens die ersten c·n Felder des Bandes benutzt. Dabei ist n die Länge des Eingabewortes und c eine konstante Zahl.

Die nutzbare Bandlänge ist somit linear in der Eingabelänge. Der konstante Faktor verändert nicht die grundsätzliche Speicherklasse: Bei längeren Eingaben wächst der nutzbare Bandbereich höchstens proportional zur Eingabe. Diese lineare Beschränkung erklärt den Bestandteil „Linear“ im Namen LBA.

Kontextsensitive Sprachen und offene Fragen

LBAs werden auch danach klassifiziert, welche Sprachen sie akzeptieren. Die Chomsky-Hierarchie ordnet Klassen formaler Grammatiken und Klassen von Automaten ein. In diesem Zusammenhang entsprechen nichtdeterministische LBAs genau den kontextsensitiven Grammatiken: Die von nichtdeterministischen LBAs akzeptierten Sprachen sind genau die kontextsensitiven Sprachen.

Mit LBAs sind zwei bekannte, auf Kuroda zurückgehende Fragestellungen verbunden, die in der englischsprachigen Literatur oft „LBA problems“ genannt werden. Die erste Frage lautet, ob jede Sprache, die von einer nichtdeterministischen LBA akzeptiert wird, auch von einer deterministischen LBA akzeptiert werden kann. Es ist also offen, ob deterministische und nichtdeterministische LBAs dieselbe Sprachklasse akzeptieren. In der Komplexitätstheorie wird dies als NSPACE(O(n)) = DSPACE(O(n))? formuliert.

Die zweite Frage betrifft die Abgeschlossenheit unter Komplementbildung: Ist die Sprachklasse der von nichtdeterministischen LBAs akzeptierten Sprachen zusammen mit jeder Sprache auch bezüglich ihres Komplements in derselben Klasse abgeschlossen? Der Satz von Immerman und Szelepcsényi beantwortet diese Frage positiv für die kontextsensitiven Sprachen (Typ 1). In entsprechender Notation lautet die Frage NSPACE(O(n)) = co-NSPACE(O(n))?.