Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
