# Minimal regular expression that matches a given set of words

I have a dictionary-like regular expression, an "or chain" of words,

word1|word2|word3|...


Unfortunately, the chain is too large. I'd like to find the minimal regular expression that is equivalent. How can do I do that?

You should think of this as a regex like /^(word1|word2|word3)\$/. I have a dictionary of words, and I want a minimal regex that will match if and only if the input string is a word in that dictionary. By minimal, I want the shortest regex that matches all words in the dictionary (and nothing else). I need a regex, not some other representation.

The words come from SQL SELECT DISTINCT word FROM t ORDER BY length DESC, word so I'm hoping for a solution that is optimized to practical use.

I was able to identify some heuristics that work for some special cases, but not a general algorithm:

• It's easy to deal with accented variations: mãe|mae becomes ma[ãe]e). This works fine.

• Also, ABCCC|ABCC|ABC|DF can be automatically reduced to (output) ABC{1,3}|DF or AB(?:C|CC|CCC)|DF

As @Raphael noted, "minimizing regular expressions is hard", so it is important the focus on non-generic solutions.

I found a web page that describes how to convert a regex to NFA or DFA, but that doesn't help me get back a minimal regular expression. I'm willing to use an existing library, such as this PHP one, but how do I use the library for this purpose?

• For your particular case(finite number of strings), it's not known if the min regular expression is NP-hard. cstheory.stackexchange.com/questions/16860/… – Chao Xu Apr 1 '17 at 23:44
• Your special case is also likely to be hard. – Yuval Filmus Apr 2 '17 at 6:54
• Don't use "EDIT:". We have revision history, so there's no need to mark your changes. Instead, make the question read well for someone who encounters it for the first time. See cs.meta.stackexchange.com/q/657/755. I've edited your question for you. Please double-check that the result matches your intent. – D.W. Jun 2 '17 at 21:16