Das Kefk Network Wiki befindet sich im Testbetrieb.

---

Aus Kefk.

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.

Automatentheorie: Formale Sprachen und Formale Grammatiken
Chomsky- Hierarchie	Grammatiken	Sprachen	Minimaler Automat
Typ-0	uneingeschränkt	rekursiv aufzählbar	Turingmaschine
	uneingeschränkt	rekursiv	Turingmaschine
Typ-1	kontextsensitiv	kontextsensitiv	linear beschränkt
Typ-2	kontextfrei	kontextfrei	Kellerautomat
Typ-3	Regulär	Regulär	Endlich
Jede Klasse einer Sprache oder Grammatik ist eine echte Teilmenge der Klasse darüber.