# Algorithm to Minimize a Regular Expression

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?

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

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

• Go over all possible regular expressions in nondecreasing order of length. For each one, check whether it is equivalent to the original regular expression. – Yuval Filmus Oct 12 at 6:30
• 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. – Yuval Filmus Oct 12 at 6:32