3
$\begingroup$

A set of English words is given. Is there linear or sublinear algorithm to build minimal DFA for the given dictionary? I tried different approaches, and they all were concerned with building Trie and then minimizing such automata. So it is very interesting for me is there some algo using it to solve my problem.

P. S. The problem must be quite common because of DFA connection with regexps, and at the same time its statement seems like special case, so I think I am missing some simple idea.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ I'm confident you can answer the sublinear part yourself. I'd prefer an explicit statement as to what is the problem size, anyway. $\endgroup$
    – greybeard
    Commented Mar 27, 2020 at 9:27

1 Answer 1

Reset to default
4
$\begingroup$

There is clearly no sublinear-time algorithm; any algorithm needs to look at all words in the input to have a hope of being correct.

There is a straightforward algorithm to construct a trie that recognizes these words in linear time. The trie is a DFA, but not a minimal DFA.

The trie is acyclic, and apparently there are algorithms for minimizing an acyclic DFA in linear time, so this yields a linear-time algorithm to construct such a minimal DFA. See for example

Johannes Bubenzer. Minimization of Acyclic DFAs. Proceedings of PSC 2011.

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.