Given an NFA, to decide if it accepts a word w, one could use the following algorithm: Transform the NFA into a DFA. Then, run w on the DFA and accept/reject if the DFA accepts/rejects.
Could this be done on a linear bounded automata? How do I know for sure that the encoding of the DFA won't go over the input space?