TM als LBA interpretieren #49
Description
In VL 20 wird eine zuvor betrachtete TM als LBA interpretiert (lecture-20.tex, ab Zeile 376). Insbesondere gibt es einen Schritt „Akzeptiere, falls der Inhalt des Bandes die Form \hat{a}^*\hat{b}^*\hat{c}^* hat“. Auf diesem Abstraktionsniveau gilt das für beide Automatenmodelle. Auf der technischen Ebene der Übergangsfunktion funktioniert aber die Erkennung des Wortendes bei beiden Automatenmodellen jeweils unterschiedlich (die TM liest und läuft nach rechts bis zum Blank; der LBA liest, markiert, und läuft nach rechts, bis ein bereits markiertes Zeichen gelesen wird). Bei der Implementierung einer TM würde vermutlich das für den LBA benötigte Verhalten nicht per se mit umgesetzt. Einen Hinweis darauf und potenzielle Folgen fände ich an dieser Stelle hilfreich.