How to reduce this regular expression?

Question

I was converting a DFA to regular expression with the help of state equations and came up with this regular expression. How do I further reduce this regular expression? $$b+aaa^*b+abb^*+a$$ I can feel it's same as $$a^*b+ab^*$$ but how do I proceed to simplify the first one to the second mathematically?

Answer 1

Minimizing a regular expression is PSPACE-hard. Therefore, if you're looking for a general set of techniques to minimize a regular expression, there's no good solution: there is no good set of techniques that always works and is always efficient. See https://cs.stackexchange.com/a/12278/755 and https://cs.stackexchange.com/a/43863/755 and https://cstheory.stackexchange.com/q/12361/5038.

Of course, none of these results rule out the possibility of techniques that work for your particular example or that sometimes work. However, they show that you shouldn't expect any general technique, i.e., any technique that works for all regular expressions and always gives the optimal answer and is asymptotically efficient.

---

That said, there are some ad-hoc methods you can use. For instance, by staring at it, you can quickly recognize that

$$abb^* + a = ab^*,$$

since $ab^* = a(b^*) = a(\varepsilon + b b^*) = a + abb^*$.