Linear beschränkte Automaten sind den anderen Automatentypen wie
Kellerautomaten, Endlichen Automaten und Turingmaschinen ähnlich.
Am meisten ähnelt ihr Aufbau dem von Turingmaschinen.
Auch sie besitzen eine Kontrolleinheit.
Sie verfügen jedoch über einen Lese-/Schreibkopf, der die Zellen des Eingabebandes nicht nur auslesen,
sondern auch beschreiben kann.
Das Eingabeband verhält sich nun eher wie ein Arbeitsband, auf dem die Zwischenergebnisse
gespeichert werden können.
Allerdings bleibt die Länge des Bandes auf die Länge der Eingabe beschränkt,
d.h. der Lese-/Schreibkopf kann sich nicht über die Anfangs- und Endmarkierungen des Eingabewortes hinaus bewegen.
Der nächste Schritt von LBA berechnet sich aus dem Inhalt der Zelle unter dem Lese-/Schreibkopf
und dem gegenwärtigen Zustand.
Ebenso wie bei einer Turingmaschine kann sich der Lese-/Schreibkopf in beiden Richtungen über dem Arbeitsband bewegen (nach rechts und nach links).
| 
Formale Darstellung von LBA
