# Space complexity for accepting word decision problem of DFAs

It is well known that the the decision problem $$w \in \mathcal{L}(M)$$ for a DFA $$M=(Q,\Sigma, \delta, q_0,F)$$ is in $$\mathcal{O}(|w|)$$. To proof this we assume that the successor state computation can be done in $$\mathcal{O}(1)$$, for example with an array of size $$Q \times \Sigma$$.

My question is: Is there a better way to store the transition function while maintaining the same runtime complexity? When $$\Sigma$$ is very large the table gets very memory inefficient. It is even worse for NFAs which have a list of states in each cell of the array.

• Usually, the encoding of $M$ would be part of the algorithm and thus not count against space complexity. Do you have someting different in mind? – Raphael Jan 21 at 12:08
• All graph representations are candidates. Variants for sparse graphs may be of particular interest. – Raphael Jan 21 at 12:09
• A standard improvement is to compute the minimal DFA, which has the least number of states. – Apass.Jack Jan 21 at 12:44
• @Raphael That is true if you ask for a specific DFA. So you would treat an algorithm which takes any $M$ and $w$ as input and checks if $w \in L(M)$ as solution to another problem? – Cilenco Jan 21 at 13:00
• Yes, definitely! In particular, you'd have to say which parameters your cost function is supposed to have. – Raphael Jan 21 at 15:38