  In programming by example, users "write" programs by generating a small
number of input-output examples and asking the computer to synthesize
consistent programs. We consider a challenging problem in this domain: learning
regular expressions (regexes) from positive and negative example strings. This
problem is challenging, as (1) user-generated examples may not be informative
enough to sufficiently constrain the hypothesis space, and (2) even if
user-generated examples are in principle informative, there is still a massive
search space to examine. We frame regex induction as the problem of inferring a
probabilistic regular grammar and propose an efficient inference approach that
uses a novel stochastic process recognition model. This model incrementally
"grows" a grammar using positive examples as a scaffold. We show that this
approach is competitive with human ability to learn regexes from examples.
