Perhaps the obvious question is "where do the regular expressions come from"? If they are generated somehow, instead of generating and then simplifying, you might find it useful to try to improve the generation process. I wonder if some of the work on grammar induction might be of use?