Suche Home Einstellungen Anmelden Hilfe  

3.2.3 Linear Beschränkte Automaten (LBA)

 
Schema eines LBA

LBA mit beidseitig begrenztem Arbeitsband

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).

1   2 Formale Darstellung von LBA

Benutzer: Gast • Besitzer: matthias • Zuletzt geändert am: