Number of states in a finite automaton How many states are required by a deterministic finite automaton to store $m$ words each of length $n$?
I came across $2^{mn}$ as the solution but there was no explanation.
 A: Denote by $s(L)$  the number of states of the minimal (deterministic) automaton of a regular language $L$. The following result is proved in [1]. Let $A$ be a two letter alphabet and let
$$
f(n) = \max \{s(L) \mid L \subseteq  A^n\}
$$
Thus $f(n)$ is the maximal number of states of the minimal automaton of a set of words of length $n$. Then 
$$
  f(n) = \sum_{0 \leq i \leq n} \min(2^i, 2^{2^{n-i}} - 1)
$$ and 
$$
1 =\liminf_{n\rightarrow \infty}\frac{nf(n)}{2^n} \leqslant \limsup_{n \rightarrow \infty}\frac{nf(n)}{2^n} = 2.
$$
For a given set of $m$ words, better bounds can be given, but $\frac{2^{n+1}}{n}$ is an upper bound for all $m$, much better than $2^{mn}$.
[1] J.-M. Champarnaud and J.-É. Pin, A maxmin problem on finite automata, Discrete Applied Mathematics 23 (1989), 91-96.
A: Though finite-state automata do not have any form of "memory" (unlike, say, pushdown automata), it is possible to use the states themselves to store a finite amount of data, in the form of $n$ bits that the automaton can access at any time.
In particular, define an n-bit automaton (not standard terminology) as something like a finite-state automaton except:


*

*In addition to an internal state, the automaton has access to n bits worth of memory.

*It can use the contents of the n stored bits to decide which transition to make.

*It can manipulate the contents of the n bits as part of the transition.
Then any n-bit automaton $A$ can be simulated by a (memoryless) finite state automaton $A'$ whose states are ordered pairs $(q,w)$, where $q$ is a state of  $A$ and $w$ is the stored binary word of length $n$.  If the $n$-bit automaton has $k$ states, then the corresponding finite-state automaton has $2^nk$ states.
An automaton that stores m binary words each of length n has a total of mn bits of memory, so each state of the mn-bit automaton corresponds to $2^{mn}$ states of the corresponding memoryless finite-state automaton.
A: 
How many states are required by a deterministic finite automaton to
  store m words each of length n?

Like J.-E. Pin seems, I too believe this means no bit words, but plain old symbol words (which only makes a difference if the alphabet has three symbols or more).
So the DFA has an alphabet $\Sigma$ and we have the task to make it accept $m$ given words $u_i \in \Sigma^n$ (thus $\lvert u_i \rvert = n$), but no other word $u \in \Sigma^*$. In this sense it would store the words.
Note: This implicitly assumes it is possible to have $m$ different words of size $n$, which would not be possible if $\Sigma$ had just one symbol.
