2
$\begingroup$

I just went to read wikipedia to check a point on FA minimization, and I read there the following sentence:

The minimal DFA ensures minimal computational cost for tasks such as pattern matching.

I have tried to imagine how, but my feeling is that DFA minimization reduces the size of the program, which is especially important when it is hardware, but will hardly do anything to speed up the computation (well, indexing states might be easier when there are less states, depending on computation model, but this seems far fetched).

Of course, from an abstract logical point of view, a minimal DFA does ensure minimal computational cost, when that same cost is ensured by any DFA for the language.

Am I missing a point? Which?

$\endgroup$
  • 3
    $\begingroup$ I think you're taking Wikipedia too literally. They probably mean that if you use DFA for implementation, then you might as well use the minimal one. $\endgroup$ – Yuval Filmus Apr 13 '15 at 18:11
  • 5
    $\begingroup$ Note the smaller programs can execute fast (consider instruction caches) but that is probably not the point here. Since it's Wikipedia, my guess is that the author of that statement did not really know their stuff. (Also, you have to construct a DFA first, and that is expensive.) $\endgroup$ – Raphael Apr 13 '15 at 21:56
  • $\begingroup$ I agree with @Raphael. Maybe the statement makes sense with NFA instead of DFA because fewer states can simplify the backtracking. $\endgroup$ – Renato Sanhueza May 9 '15 at 3:47
  • $\begingroup$ @babou If the automaton is deterministic no backtracking occurs so minimizing the automata will not reduce the computational cost of pattern matching. In other hand if you minimize a NFA you can have some reduction in computational cost although minimizing NFA is harder than minimizing a DFA. $\endgroup$ – Renato Sanhueza May 9 '15 at 14:08
  • $\begingroup$ @RenatoSanhueza Raphael's point was that a smaller program may execute faster, so that the smallest deterministic automaton may be faster, but I fear that non-determinism is usually a speed killer, whatever the size. There may be counter-examples, but ... $\endgroup$ – babou May 9 '15 at 14:13

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.