In the world of regular languages, finding the minimal DFA is a well-understood problem with a reasonably efficient implementation.For NFAs and regular expressions this is substantially harder.Yes, one can devise an algorithm which, given a regular expression, computes the smallest regular expression that has the same language, but that algorithm would compete with the definitely-best-chess-move program in the category of programs that hardly ever answer in real time.
So, what can be done, with "realistic" efforts?We have built a hierarchy of increasingly powerful transformations that tackle the issue. We explain how these transformations have been realised, as algebraic manipulations in other problem domains could often be done in a similar vein.
It turns out that on truly random regular expressionsO(n log n) trafos move very close to what is possible.Indeed, there is even such a thing as the "average size of a normal form"that is not infinity, at least for small alphabets.Joint work with Colin Runciman
Cornwallis South West,
University of Kent,