HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Minimizing DFA built on set of words

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
builtdfaminimizingwordsset

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#122199, answer score: 4

Revisions (0)

No revisions yet.