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.

  • $\begingroup$ 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? $\endgroup$ – Raphael Jan 21 at 12:08
  • $\begingroup$ All graph representations are candidates. Variants for sparse graphs may be of particular interest. $\endgroup$ – Raphael Jan 21 at 12:09
  • $\begingroup$ A standard improvement is to compute the minimal DFA, which has the least number of states. $\endgroup$ – Apass.Jack Jan 21 at 12:44
  • $\begingroup$ @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? $\endgroup$ – Cilenco Jan 21 at 13:00
  • $\begingroup$ Yes, definitely! In particular, you'd have to say which parameters your cost function is supposed to have. $\endgroup$ – Raphael Jan 21 at 15:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.