Interestingly, finding a minimal-size regexp satisfying a set of positive and negative examples (words that should match, and should not match) is NP-hard. Here

Interestingly, finding a minimal-size regexp satisfying a set of positive and negative examples (words that should match, and should not match) is NP-hard. Here is a nice discussion: http://cstheory.blogoverflow.com/2011/08/on-learning-regular-languages/ http://cstheory.blogoverflow.com/2011/08/on-learning-regular...