Are you familiar with the work of the Machine Learning Lab at the University of Trieste? And, if so, could you quickly comment on how the two approaches differ?
Yeah their work is very cool! The two tasks are a bit different however. Their system is for the task of generating regular expressions given a set of positive and negative examples of what the regex should match. It uses genetic algorithms and other techniques to optimize and search for a regex that fits all the given examples.
In our case, we have no examples to test against, only a natural language (English) description of what the user wants the regex to do. This is an inference problem more than a search problem as we've got one shot to give our best guess without any tests to check against and modify our answer.
http://machinelearning.inginf.units.it/
http://regex.inginf.units.it/