Comment on Python code to solve xkcd 1313 by Peter NorvigComments−a3_nm12yInterestingly, 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...
Comments
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...