Can we call deterministic equivalent of all NFA to be finite

Question

Finite automata is defined as a simple machine having small memory. A deterministic equivalent of a NFA with n states will have O(2^n) states,so the number of states grow exponentially. So can we always call the deterministic equivalent to be a finite automata just by saying that as n is finite 2^n will also be finite even though the actual memory will be very large or is there some limitation?

Answer 1

Finite automata is defined as a simple machine having small memory.

In fact, they are not defined in this way. You can look up the actual definition on Wikipedia. Even as an informal definition, the adjective small is inappropriate here — in fact, DFAs and NFAs have constant memory.

You are using the letter $n$ to represent the number of states in a finite automaton. The letter $n$ is usually reserved for the input length. The number of states in a finite automaton doesn't depend on the length of the input. On the contrary, the number of states is fixed ahead of time, and the finite automaton then uses exactly the same number of states for any input, of any length. Perhaps it will be less confusing if you use a different symbol, say $m$.

... the actual memory will be large ...

In theoretical computer science, there are no arbitrary constants thrown around. Today, $2^{50}$ bytes of memory can be considered large, but next year it might be $2^{60}$ bytes of memory. The same theory should account for both. In theoretical computer science, the formal meaning of large (or, more accurately, super-constant), is "tending to infinity with $n$", where $n$ is the input length. Finite automata use a fixed amount of memory which is independent of the input length, and so they never use a large amount of memory, as far as theorists are concerned.

In practice, some automata are too big to actually implement. But this is a practical restriction rather than a restriction on the actual definition.