{"id":1401,"date":"2011-04-16T15:41:14","date_gmt":"2011-04-16T19:41:14","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/?p=1401"},"modified":"2011-04-16T15:41:14","modified_gmt":"2011-04-16T19:41:14","slug":"regular-expressions-and-derivatives","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2011\/04\/16\/regular-expressions-and-derivatives\/","title":{"rendered":"Regular Expressions and Derivatives"},"content":{"rendered":"

When you’re working with regular languages specified in regular expression form, there’s a really cool idea that you can use for building regular expression matchers, and for describing how to convert from a regular expression to a NFA. It’s called the Brzozozwksi derivative<\/em> of a regular expression – or just simply the derivative of a regexp.<\/p>\n

The basic idea of the derivative is that given a regular expression, r, you can derive a new regular expression called the derivative with respect to symbol c, D_c(r). D_c(r) is a regular expression describing the string matched by r after<\/em> it’s matched an r.<\/p>\n

<\/p>\n

To define the derivative, we first need a helper, which we’ll call delta. What delta does is tell us if a given regular expression canmatch the empty string. We’ll use it a few ways – both as a part of the derivative, and as part of the process of turning a regular expression into a finite state machine. For convenience, we’ll define it so that delta(r) returns epsilon (a pattern matching the empty string) if r can match the empty string, or emptyset (the null pattern, a regular expression which never matches anything) if it can’t.<\/p>\n

Given a regular expression r, we define delta(r) as follows:<\/p>\n