Learning finite automata. Early work on the subject leveraged Hidden Markov Models [1]} and probabilistic finite state machines [2]} as the models for learning.
Later approaches readily recognized the utility of regular expressions as a form for description and tended to be deterministic.
Polynomial-time algorithms were proposed for learning of regular expressions without union operation from chosen classes of positive examples [3]} and for learning of unambiguous regular expressions of maximum loop depth 2 [4]}. A genetic programming approach leveraging both positive and negative examples was used in [5]}, and a further polynomial-time method for 1-unambiguous regular expressions aiming for simplicity of the resulting expressions was presented in [6]}.
Most of the recent work on regular expression learning takes the line of natural language processing (NLP) and proposes methods for particular uses in real-world datasets.
A genetic programming method for text extraction from XML documents is outlined in [7]}.
[8]} focuses on identifying email campaigns with high precision while phrasing it as an optimisation problem, and [9]} gives a method based on Support-Vector Machines tailored to clinical texts.
