Eine formale Beschreibung eines LBA muss die veränderte Rolle des Arbeitsbandes und die neue Bewegungsfreiheit des
Lese-/Schreibkopfes berücksichtigen.
Zu den Komponenten gehören das Bandalphabet, von dem ein Teil das Eingabealphabet ist;
die Zustände, die der LBA einnehmen kann;
den Startzustand aus der Menge der Zustände;
die Menge der Endzustände - eine Teilmenge der Zustände;
zwei besondere Symbole, die das Band links und rechts von der Eingabe begrenzen,
und die Übergangsfunktion.
Die Übergangsfunktion ordnet einem Paar <aktueller Zustand, aktuelles Eingabezeichen> ein Tripel
<neuer Zustand, zu schreibendes Symbol, Bewegung des Lese-/Schreibkopfes> zu.
Diese Abbildung muss nicht vollständig definiert sein.
Bei einem LBA ist keine Bewegung über die Wortendmarkierungen hinaus möglich.
Zur Sprache eines LBA gehören alle Wörter aus dem Eingabealphabet, für die der Automat
durch eine Folge von Operationen (definiert durch die Übergangsfunktion) einen Endzustand erreicht.
Aufgrund der Beschränkungen des Arbeitsbandes,
akzeptiert ein LBA nur Wörter, die bei der Analyse nicht mehr Speicherplatz benötigen als die anfängliche Wortlänge.
| 
1
2
Übersicht: Sprachklassen
