Synthesizing regular expressions from examples for introductory automata assignments

Mina Lee, Sunbeom So, Hakjoo Oh

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)


We present a method for synthesizing regular expressions for introductory automata assignments. Given a set of positive and negative examples, the method automatically synthesizes the simplest possible regular expression that accepts all the positive examples while rejecting all the negative examples. The key novelty is the search-based synthesis algorithm that leverages ideas from over- and under-approximations to effectively prune out a large search space. We have implemented our technique in a tool and evaluated it with non-trivial benchmark problems that students often struggle with. The results show that our system can synthesize desired regular expressions in 6.7 seconds on the average, so that it can be interactively used by students to enhance their understanding of regular expressions.

Original languageEnglish
Pages (from-to)70-80
Number of pages11
JournalACM SIGPLAN Notices
Issue number3
Publication statusPublished - 2016 Oct 20


  • Regular expression
  • program synthesis
  • programming by example

ASJC Scopus subject areas

  • General Computer Science


Dive into the research topics of 'Synthesizing regular expressions from examples for introductory automata assignments'. Together they form a unique fingerprint.

Cite this