Linear Bounded Automaton: Definition
Definition: A linear bounded automaton (LBA) is a TM that cannot extend its tape by any rule.
 Gist:
With w on its tape, M’s tape is restricted to |w| squares.
32/45
Accepted language: Illustration
w
s
x
y
f
D
D
The same length.