1
$\begingroup$

I am referring to regular expressions with alphabet {$0$, $1$}. We want to minimize them so that they have the least possible number of symbols and operators. Is there an algorithm to do this?

For instance, what is done on this page in the accepted answer:

https://stackoverflow.com/questions/35112630/minimize-specific-regular-expression

Is there a formal algorithm to explain the process that the answer went through?

$\endgroup$
  • $\begingroup$ Go over all possible regular expressions in nondecreasing order of length. For each one, check whether it is equivalent to the original regular expression. $\endgroup$ – Yuval Filmus Oct 12 at 6:30
  • 1
    $\begingroup$ Finding the minimum length of an equivalent regular expression, or even approximating it, is known to be NP-hard, so minimizing regular expressions is computationally hard. $\endgroup$ – Yuval Filmus Oct 12 at 6:32
0
$\begingroup$

There is a trivial algorithm to find the minimum regular expression equivalent to a given one:

Go over all regular expressions in nondecreasing order of length. For each one, check whether it is equivalent to the original regular expression. Return the first one which is.

To check equivalence, convert the regular expressions to NFAs, then to DFAs, then computed the product automaton for the symmetric difference, and check whether any accepting state is reachable from the initial state.

This algorithm isn't very efficient. Indeed, minimizing regular expressions is PSPACE-complete. See for example Gramlich and Schnitger, Minimizing nfa's and regular expressions.

$\endgroup$
  • $\begingroup$ "isn't very efficient" is a stunning understatement. $\endgroup$ – Rick Decker Oct 14 at 0:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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