Unbounded Space Computations
Cannot construct an FSM that checks if an input string is of the form anbn, n > 0 (e.g., ab, aabb, … )
After processing the a symbols in the sequence, we
need to remember the number of a symbols to check
that there are an equal number of subsequent b
A finite state machine cannot remember an unbounded