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.