I'm looking for a program such that, given a finite list of strings, can find short regexes to match exactly all of them and nothing else.

Since there are multiple languages that express regexes differently, there can correspondingly be multiple regex generators. Each answer must discuss regex generation in one langauge only (or a family of languages for which there is a direct correspondence between regexes in each of them).

  • 1
    \$\begingroup\$ @Arnauld Yeah, I thought the "exactly" made it clear enough. Edited. \$\endgroup\$ May 19 '20 at 11:55
  • 3
    \$\begingroup\$ Another useful feature of such a tool would be to generate a regex that matches all strings in a list A but not any of the strings in a list B, with undefined behavior for any other input. (This is what I would have needed to optimize this handcrafted answer.) \$\endgroup\$
    – Arnauld
    May 19 '20 at 20:48
  • 1
    \$\begingroup\$ @ghosts_in_the_code to write code implementing it without reducing it(code). \$\endgroup\$ Jul 21 '20 at 10:27
  • 1
    \$\begingroup\$ @VictorVosMottorthanksMonica oh yeah the regex generator doesn't have to be golfed \$\endgroup\$ Jul 21 '20 at 10:33
  • 1
    \$\begingroup\$ Seems NP-hard. \$\endgroup\$
    – Adám
    Jul 27 '20 at 10:33

The Machine Learning Lab at the University of Trieste, Italy, wrote a web app to solve this exact problem, available at: Automatic Generation of Regular Expressions from Examples based on "genetic programming" and published a paper about it. Based on the fact that it had to come from the Machine Learning Lab of a university in Italy, and was worth publishing a paper about, it is probably a pretty hard problem to solve. Doesn't sound like the type of question for Code Golf SE, but I'm new here, so I wouldn't be the expert on that.

  • \$\begingroup\$ Welcome to the site. That's a cool approach to regex generation. Note, though, that the app isn't guaranteed to find the shortest possible regex. From the FAQ: '3. The generated regexes look unoptimized. Why? There are some optimization which could make a given regex appear better, e.g., [\d\d\.\d][\d\.]. Currently, our prototype does not apply any of these optimizations.' Nor will the generated regex match only the given strings and nothing else. You are right - this is a hard problem. \$\endgroup\$
    – Dingus
    Aug 19 '20 at 2:58
  • \$\begingroup\$ I didn't look into it, but the description of the website I linked does include "old version", so maybe there is a newer version which does apply the optimizations? I seem to remember the website looking different the first time I saw it than this time around, so maybe I really did link an old one... \$\endgroup\$
    – Sam
    Aug 19 '20 at 3:03
  • \$\begingroup\$ I believe I linked to the "Regex Generator" page, here is the "Regex Generator++" page: regex.inginf.units.it . I updated the post. I wonder if the ++ version does perform the optimizations... \$\endgroup\$
    – Sam
    Aug 19 '20 at 15:58
  • \$\begingroup\$ I believe that the ++ version does perform the optimizations. At least, in the regex golf section - which looks more similair in its UI to the ++ version - it has a stage when it is figuring out the Regex where it says "Optimizing..." \$\endgroup\$
    – Sam
    Aug 19 '20 at 19:43

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.