I have a blackbox program that generates a set of strings. What is the best regular expression learner that I can use to learn (approximate) what the blackbox program uses as a generator? Note that I only have positive examples. (Checking whether a string is accepted or rejected is possible but rather costly). I see that algorithms like RPNI and L* requires both positive and negative examples.

I especially want to avoid over-generalization.

Update: I have been making do with using Sequitur to identify repeating patterns in single strings, and then lining up the resulting patterns to identify common repetitions. However, this feels really kludgy and I would like to improve it. Is this the best one can do? are there better ways?

  • $\begingroup$ Without negative examples, the problem seems to be ill-defined. If you ask for the simplest regex then it will be .*, which overgeneralises. If you ask for the most specific regex, it will be word1|word2|...|wordn. Since you use the word example, I assume that this would be too specific. Do you have any ideas for criteria to say which of two candidate regexes is "better"? $\endgroup$ – Peter Taylor May 20 at 8:41
  • $\begingroup$ So, the problem is to approximate the generator which may be using a regex to generate the inputs. So, even though the algorithm requested can not know of the original regex, we (examiners) can use the regex inside the blackbox to determine if the learned regex is correct (or if it over or under generalizes). Does this help? There does seen to be some research (e.g. core.ac.uk/download/pdf/81942815.pdf) in this regard; so it is reasonably well defined. But I would like to know where the field is at. $\endgroup$ – rahul May 20 at 9:14
  • $\begingroup$ The problem is a rather classical one. See en.wikipedia.org/wiki/Language_identification_in_the_limit for references including one to Gold's original paper. $\endgroup$ – Kai May 20 at 9:52
  • $\begingroup$ @kai Indeed. Gold shows that learning with positive examples only is impossible. However, what is the best one can do? $\endgroup$ – rahul May 20 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.