So if we have a complex equation in regular algebra we can use properties like distrbuivity, associativity and commutativity to make an equation simper or more compact.

Can we use some sort of techniques on regular expressions to make them more simpler?

For example what is the relation between concatenation and kleene star? If we have a concatenation with an union between two expressions that have kleene star can we draw a conclusion using some sort of property to distribute the concatenation somehow or do something else. I just started learning this subjects and I may not be very good at expressing what I think right now.


1 Answer 1


Minimizing regular expressions is very hard, see for example a paper of Gramlich and Schnitger, who show that no $o(n)$ approximation algorithm exists unless P=PSPACE. Another type of answer to your question is the formal systems mentioned in my answer to your related question.


Your Answer

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

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