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?
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.