Kleines Nachschlagewerk Informatik
linear beschränkte Automaten
Worum geht es?
Bisher wurden die Automaten um einen einfachen Speicher erweitert. Dieser war nicht frei adressierbar. Diese Einschränkung soll nun aufgehoben werden.
Linear beschränkte Automaten
Ein endlicher Automat wird so erweitert, dass er wahlfreien Zugriff auf den Speicher, der das Eingabewort enthält, erhält. Der Speicher darf nicht größer sein als das zu verarbeitende Eingabewort.

Achtung, der Kellerautomat hatte eine Eingabe und einen Kellerspeicher. Diese waren getrennt. Jetzt liegt die Eingabe im Speicher.
Darstellung linear beschränkter Automaten
Hier kann man die Darstellung von Turingmaschinen nutzen und entsprechend reduzieren. Siehe deshalb dort.