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


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?

  • 1
    $\begingroup$ 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/… $\endgroup$
    – Chao Xu
    Apr 1, 2017 at 23:44
  • $\begingroup$ Your special case is also likely to be hard. $\endgroup$ Apr 2, 2017 at 6:54
  • $\begingroup$ @Chao Xu: please consider converting your comment into an answer. As you stated, it is an unresolved research problem in theoretical computer science. $\endgroup$ Nov 24, 2019 at 21:34
  • 1
    $\begingroup$ The second example of simplification the OP found is referred to as "analogue to Horner's rule" in: Keith Ellul, Bryan Krawetz, Jeffrey Shallit, Ming-wei Wang: Regular Expressions: New Results and Open Problems. Journal of Automata, Languages and Combinatorics 10(4): 407-437 (2005) $\endgroup$ Nov 24, 2019 at 21:42


Your Answer

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