Grammatical inference of regular expressions for given finite list of representative strings?

by

Yes, it turns out this does exist; what is required is what is known academically as a DFA Learning algorithm, examples of which include:

  • Angluin’s L*
  • L* (adding counter-examples to columns)
  • Kearns / Vazirani
  • Rivest / Schapire
  • NL*
  • Regular positive negative inference (RPNI)
  • DeLeTe2
  • Biermann & Feldman’s algorithm
  • Biermann & Feldman’s algorithm (using SAT-solving)

Source for the above is libalf, an open-source automata learning algorithm framework in C++; descriptions of at least some of these algorithms can be found in this textbook, among others. There are also implementations of grammatical inference algorithms (including DFA learning) in gitoolbox for MATLAB.

Since this question has come up before and has not been satisfactorily answered in the past, I am in the process of evaluating these algorithms and will update will more information about how useful they are, unless someone with more expertise in the area does first (which is preferable).

NOTE: I am accepting my own answer for now but will gladly accept a better one if someone can provide one.

FURTHER NOTE: I’ve decided to go with the route of using custom code, since using a generic algorithm turns out to be a bit overkill for the data I’m working with. I’m leaving this answer here in case someone else needs it, and will update if I ever do evaluate these.

More Related Contents:

  1. Regular expression [ 1 ( 0 1* 0)* 1 ]* DFA
  2. Finding the complement of a DFA?
  3. Design DFA accepting binary strings divisible by a number ‘n’
  4. What is the best regular expression to check if a string is a valid URL?
  5. Why it’s not possible to use regex to parse HTML/XML: a formal explanation in layman’s terms
  6. Getting parts of a URL (Regex)
  7. How does Stack Overflow generate its SEO-friendly URLs?
  8. Is there something like a counter variable in regular expression replace?
  9. Collapse and Capture a Repeating Pattern in a Single Regex Expression
  10. What is the best regular expression to check if a string is a valid URL?
  11. Random string that matches a regexp [duplicate]
  12. Match linebreaks – \n or \r\n?
  13. Is it possible for a computer to “learn” a regular expression by user-provided examples?
  14. Regular Expression Vs. String Parsing
  15. What is a Context Free Grammar?
  16. Regular expressions Equivalence
  17. Regex BNF Grammar
  18. Why do regex engines allow / automatically attempt matching at the end of the input string?
  19. How to order regular expression alternatives to get longest match?
  20. Regex: match everything but a specific pattern
  21. Regular Expression for alphanumeric and underscores
  22. How to match multiple occurrences of a substring
  23. Find and kill a process in one line using bash and regex
  24. Regex: matching up to the first occurrence of a character
  25. Convert a char to upper case using regular expressions (EditPad Pro)
  26. How to check if a line is blank using regex
  27. R dplyr: rename variables using string functions
  28. What does ?= mean in a regular expression?
  29. Regular Expressions with repeated characters
  30. R split on delimiter (split) keep the delimiter (split)

Leave a Comment