Sei \( n \in \mathbb{N} \) und \( w \) ein Eingabewort. Ein \( n \)-beschränkter Automat ist eine indeterminierte 2-NTM, die auf dem Eingabeband (das einen beliebigen Input \( w \) enthalten kann) nur lesen darf und ein Arbeitsband der Länge \( n \) zur Verfügung hat. Ein linear beschränkter Automat LBA ist eine indeterminierte 2-NTM, die auf dem Eingabeband (das einen beliebigen Input \( w \) enthalten kann) nur lesen darf und ein Arbeitsband der Länge \( |w| \) zur Verfügung hat.
(a) \( \left.{ }^{(* *}\right) \) Sei \( n \in \mathbb{N} \) fest und sei \( L \) eine durch einen \( n \)-beschränkten Automaten akzeptierbare Sprache. Zeigen Sie, dass \( L \) dann auch entscheidbar ist. ( \( L \) ist dann sogar regulär!)
(b) \( \left(^{* * *}\right) \) Zeigen Sie, dass die Klasse der von LBAen akzeptierbaren Sprachen echt grösser ist, als die Klasse der kontextfreien Sprachen. (LBAen erkennen nämlich genau die kontextsensitiven Sprachen!)
(c) \( \left(^{* * * *}\right) \) Zeigen Sie, dass das folgende Problem unentscheidbar ist: Ist eine gegebene 2-NTM ein LBA?
